2019山东省赛B - Flipping Game ZOJ - 4114 题解
题意：
初始有n个灯泡，灯泡状态是0和1,。现在有k***作，每次改变且仅改变m个的灯的状态，给定n盏灯的初始状态的最终状态，求有多少种解决改变灯的方案满足可以满足题目条件。
思路：
开始写的时候以为是组合计数和容斥原理什么鬼的，后来发现n，m，k的值都比较小，觉得应该是三维dp了，当然是瞎想，最后看题解还是一个二维dp可以解决的问题，只不过是三重循环。给队友lrr说了一下题解的状态定义，他也较快就写出来了。其实对于灯的状态，每次改变一次之后，现在的问题和之前的问题形式一样，只是k值和目标灯的状态不同的个数变了。
状态如下定义dp【i】【j】表示操作到第 i 轮，与目标的灯的状态不同的个数为 j 的操作方案数量。初始化dp[k][0]=1,dp[k][others]=0。倒退dp的状态转移，对于第k-1次，他的方案数是第k次全部的dp数组（即dp【k】）中转移而来的。对于dp[k][j]，与目标状态j的不同，n-j个相同，设改变j个中的x个，改变n-j个中的y个（这里要求x+y=m&& j-x+y=kk）(kk为dp【k】中与目标状态不同的个数为kk)。这样可以解出x和y，当x和y满足为整数并且x<=j&&y<=n-j 即为合理的转移方案。这样dp转移就不存在什么重复计数的问题，因为都是一种存在的状态变化而来的，计算出到达每种状态的方案数量，最后的答案就是dp[0][ans]，ans为初始与目标状态不同的灯泡数量。
接下来思考为什么要这样设计状态，可能是由于灯泡的特殊性，具体也不太清楚。
代码：
#include<iostream> #include<stdio.h> #include<math.h> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int MAX_N=1e5+5; const int M=998244353; int n,k,m; ll dp[105][105]; ll fac[105],inv_fac[105]; ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1)res=res*x%M; x=x*x%M; n>>=1; } return res; } void init(){ fac[0]=1; for(int i=1;i<105;i++){ fac[i]=fac[i-1]*i%M; } inv_fac[104]=mod_pow(fac[104],M-2); for(int i=103;i>=0;i--){ inv_fac[i]=inv_fac[i+1]*(i+1)%M; } } ll C(int n,int m){ return fac[n]*inv_fac[n-m]%M*inv_fac[m]%M; } void fun(int ans){ memset(dp,0,sizeof(dp)); for(int i=0;i<105;i++)dp[k][i]=0; dp[k][0]=1;//only the same is ok for(int i=k-1;i>=0;i--){ for(int j=0;j<=n;j++){ for(int kk=0;kk<=n;kk++){ int x=m-kk+j; int y=kk+m-j; if(x%2==0&&y%2==0&&x/2<=j&&x/2>=0&&y/2<=n-j&&y/2>=0) dp[i][j]=(dp[i][j]+dp[i+1][kk]*C(j,x/2)%M*C(n-j,y/2)%M)%M; } } } printf("%lld\n",dp[0][ans]); } int main() { init(); int T; scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&k,&m); string s1,s2; cin>>s1>>s2; int ans=0; for(int i=0;i<s1.length();i++){ if(s1[i]!=s2[i])ans++; } fun(ans); } return 0; }
查看8道真题和解析
