題意：

　　初始有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 okfor(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; }

?

轉載于:https://www.cnblogs.com/gzr2018/p/10882754.html

總結

以上是生活随笔為你收集整理的2019山东省赛B - Flipping Game ZOJ - 4114 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。