ZOJ - 4114 Flipping Game

　　题目大意：给出两个串s,t，n个灯泡的序列，1代表开着，0代表关着，一共操作k轮，每轮改变m个灯泡的状态，问最终能把s串变成t串的方案数。

　　坤神题解。

　　很奇特的一种dp，首先状态的定义dp[i][j]是前i轮操作后，有j个灯泡的状态跟最终串不一样的方案数。这样初始化是dp[0][num]=1其他全0，num是s串和t串状态不同的灯泡数目。然后状态的转移，对于每一轮我们枚举有j个灯泡跟最终串状态不一样，然后再枚举上一轮有kk个灯泡与最终串状态不一样，每次操作都会改变灯泡的状态，设上一轮不一样的状态改变了x个，一样的状态改变了y个，那么x,y应该有0<=x<=kk,0<=y<=n-kk，x+y=m,kk-x+y=j,这四个约束条件，而满足约束条件的就是合法的转移过程，也就是dp[i][j]=dp[i-1][kk]*C[kk][x]*C[n-kk][y]，最后注意取模。

#include
typedef long long ll;
const int N=,mod=;
ll dp[N][N],C[N][N];
char a[N],b[N];
void getC()
{
C[][]=1ll;
for(int i=;i<=;i++) { C[i][]=1ll; for(int j=;j<=i;j++) { if(j<=i/) C[i][j]=C[i-][j]+C[i-][j-]; else C[i][j]=C[i][i-j]; if(C[i][j]>=mod)
C[i][j]%=mod;
}
}
}
void init(int n,int k)
{
for(int i=;i<=k;i++) for(int j=;j<=n;j++) dp[i][j]=0ll; int num=; for(int i=;ikk||y>n-kk)
continue;
dp[i][j]+=dp[i-][kk]*C[kk][x]%mod*C[n-kk][y]%mod;
if(dp[i][j]>=mod)
dp[i][j]%=mod;
}
printf("%lld\n",dp[k][]);
}
return ;
}

神奇的dp