【-20】agc 013D-Piling Up

Problem Statement

Joisino has a lot of red and blue bricks and a large box. She will build a tower of these bricks in the following manner.

First, she will pick a total of $N$ bricks and put them into the box. Here, there may be any number of bricks of each color in the box, as long as there are $N$ bricks in total. Particularly, there may be zero red bricks or zero blue bricks. Then, she will repeat an operation $M$ times, which consists of the following three steps:

Take out an arbitrary brick from the box.
Put one red brick and one blue brick into the box.
Take out another arbitrary brick from the box.
After the M operations, Joisino will build a tower by stacking the $2×M$ bricks removed from the box, in the order they are taken out. She is interested in the following question: how many different sequences of colors of these $2×M$ bricks are possible? Write a program to find the answer. Since it can be extremely large, print the count modulo $10^9+7$.

Constraints

$1≤N≤3000$
$1≤M≤3000$

Input

Input is given from Standard Input in the following format:

$N M$
Output
Print the count of the different possible sequences of colors of $2×M$ bricks that will be stacked, modulo $10^9+7$.

Sample Input 1

2 3

Sample Output 1

56
A total of six bricks will be removed from the box. The only impossible sequences of colors of these bricks are the ones where the colors of the second, third, fourth and fifth bricks are all the same. Therefore, there are $26−2×2×2=56$ possible sequences of colors.

Sample Input 2

1000 10

Sample Output 2

1048576

Sample Input 3

1000 3000

Sample Output 3

693347555

题解

题目大意:
在箱子里放n个球,有黑白两色。执行m轮操作:
1.抓箱子里一个球堆在塔顶。
2.往箱子里放入一个黑球和一个白球。
3.再抓箱子里的一个球堆在塔顶。
求塔的方案数

模型转换:

Flowey 是一朵能够通过友谊颗粒传播 LOVE 的小花.它的友谊颗粒分为两种,
圆粒的和皱粒的,它们依次排列组成了一个长度为 $2m$ 的序列.对于一个友谊颗
粒的序列,如果存在 $1≤i<j≤2m$ ,满足以下条件:
1) $i$ 为偶数, $j$ 为奇数
2)第 $i$ 颗友谊颗粒和第 $j$ 颗友谊颗粒同为圆粒或同为皱粒
3)第 $i$ 颗友谊颗粒和第$ $j 颗友谊颗粒都还没有被使用过
那么,就可以使用这两颗友谊颗粒,然后提升一次 LV.
定义一个友谊颗粒的序列为高效的,当且仅当尽可能多的提升 LV 后,序列
上剩余的友谊颗粒数量不超过 $2n$。
现在,Flowey 想知道,长度为 $2m$ 的友谊颗粒序列,有多少个不同的序列是
高效的?
定义两个友谊颗粒序列是不同的,当且仅当存在 $1≤i≤2m$,第 $i$ 颗友谊颗粒在
一个序列中为圆粒,而在另一个中为皱粒.
由于答案可能很大,你只需要求出答案对 $p$ 取模的结果.

于是我们吧圆粒和皱粒用0和1表示,每次一对一对的加,只有4种方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=3010;
int n,m;
const int p=1000000007;
int f[maxn][maxn][2];//f[i][j][k] j:偶数位0失配数
int ans;
int main()
{
n=read();m=read();
f[0][0][1]=1;
for (int i=1;i<=n;i++) f[0][i][0]=1;//初始化
for (int i=0;i<m;i++)
for (int j=0;j<=n;j++)
for (int k=0;k<=1;k++)
{//j!=0:前面有未匹配的偶数位的0需要匹配 j==1:自己是0点
if (j) (f[i+1][j-1][k|(j==1)]+=f[i][j][k])%=p;//加入01
if (j) (f[i+1][j][k|(j==1)]+=f[i][j][k])%=p;//加入00
if (n-j) (f[i+1][j+1][k]+=f[i][j][k])%=p;//加入10
if (n-j) (f[i+1][j][k]+=f[i][j][k])%=p;//加入11
}
for (int i=0;i<=n;i++) //只统计经过了0点的
{
ans+=f[m][i][1];
if (ans>p) ans-=p;
}
if (ans>p) ans-=p;
printf("%d\n",ans);
return 0;
}