题目大意:给出两个串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<cstdio>
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=;i<n;i++)
num+=(a[i]!=b[i]);
dp[][num]=;
}
int main()
{
int t,n,m,k,x,y;
getC();
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&k,&m);
scanf("%s%s",a,b);
init(n,k);
for(int i=;i<=k;i++)
for(int j=;j<=n;j++)
for(int kk=((m+j)&);kk<=m+j&&kk<=n;kk+=)
{//把约束条件联立一下可以得出合法条件下的x,y
y=(m+j-kk)/;
x=m-y;
if(x<||y<||x>kk||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