题目大意
有两种元素，一种0一种1，一开始，你可以随便拿01，总共拿n个。 然后你进行m次操作，每次操作先从手上拿一个元素，放在你的构造序列末尾，然后再获得0,1各一个，然后再放一次。 问最后有多少种不同的序列。 n,m<=3000
解题思路
一个很简单的想法是设f[i][j]表示做了第i轮，剩下j个0的时候，有多少种不同的序列。 然后根据题意转移。 但是如果直接把f[0][0~n]=1，那么就会出现一种序列被多个初始状态转移到。 考虑去重。我们让一种序列归进初始0最少的状态里，那么肯定在中途出现过0刚好用完的情况。 那么多开一维即可，表示这个状态在之前的转移的时候有没有出现过0用完。 复杂度O(nm)
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=
1e6+
5,M=
2e6+
5,mo=
1e9+
7;
ll f[
3005][
3005][
2];
int n,m,i,j,k,ans;
int main()
{
freopen(
"t7.in",
"r",stdin);
scanf(
"%d %d",&n,&m);
fo(i,
0,n) f[
0][i][i==
0]=
1;
fo(i,
0,m-
1)
fo(j,
0,n)
fo(k,
0,
1)
{
if (j) (f[i+
1][j-
1][k|(j==
1)]+=f[i][j][k])%=mo;
if (j) (f[i+
1][j][k|(j==
1)]+=f[i][j][k])%=mo;
if (n-j) (f[i+
1][j+
1][k]+=f[i][j][k])%=mo;
if (n-j) (f[i+
1][j][k]+=f[i][j][k])%=mo;
}
fo(i,
0,n) ans=(ans+f[m][i][
1])%mo;
printf(
"%d\n",ans%mo);
}
