Flipping Game（DP+组合数）

佚名 6年前 (2019-05-13) 随笔 757人围观抢沙发百度已收录

题目链接：https://cn.vjudge.net/problem/ZOJ-4114

题目大意：给你n个开关，一共是kk轮，一轮可以关m个灯（这m个灯必须都不同），问你有多少种方法能从初始状态到达最终状态。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

具体思路：dp[i][j] 表示到第i轮的时候，当前正确的为j的这种情况有多少个。

i ： 1->kk

j ： 0->m

k：0->n

dp[ i ][ k - j + m - j ] += dp[ i - 1 ][ k ] * C(k,j) * C( n - k , m - j).

第i轮，合法的从k正确的里面选出j个合法的变成非合法的，然后从剩余的n-k个中选择m-j个非法的变成合法的。

AC代码：

 1 #include<bits/stdc++.h>  2 using namespace std;  3 # define ll long long  4 # define inf 0x3f3f3f3f  5 const int maxn = 2e5+100;  6 const int N = 100+10;  7 const ll mod = 998244353;  8 char str1[maxn],str2[maxn];  9 ll dp[N][N]; 10 ll fac[N],inv[N]; 11 ll qsm(ll t1,ll t2) 12 { 13 ll ans=1ll; 14 while(t2) 15  { 16 if(t2&1) 17 ans=ans*t1%mod; 18 t1=t1*t1%mod; 19 t2>>=1; 20  } 21 return ans; 22 } 23 24 void init() 25 { 26 fac[1]=fac[0]=1ll; 27 for(ll i=2; i<N; i++) 28  { 29 fac[i]=(fac[i-1]*i)%mod; 30  } 31 inv[N-1]=qsm(fac[N-1],mod-2ll); 32 for(ll i=N-2; i>=0; i--) 33  { 34 inv[i]=(inv[i+1]*(i+1ll))%mod; 35  } 36 } 37 ll C(ll n,ll r) 38 { 39 if(r==0||n==r) 40 return 1ll; 41 return (fac[n]*inv[r]%mod*inv[n-r]%mod)%mod; 42 } 43 int main() 44 { 45  init(); 46 int T; 47 scanf("%d",&T); 48 while(T--) 49  { 50 memset(dp,0,sizeof(dp)); 51 int n,kk,m; 52 scanf("%d %d %d",&n,&kk,&m); 53 scanf("%s",str1); 54 scanf("%s",str2); 55 int len1=strlen(str1); 56 int len2=strlen(str2); 57 int num=0; 58 for(int i=0; i<len1; i++) 59  { 60 if(str1[i]==str2[i]) 61 num++; 62  } 63 dp[0][num]=1ll; 64 for(ll i=1; i<=kk; i++) 65  { 66 for(ll j=0; j<=m; j++) 67  { 68 for(ll k=0; k<=n; k++) 69  { 70 if(k-j>=0&&(n-k)>=(m-j)) 71  { 72 dp[i][k-j+m-j]=(dp[i][k-j+m-j]+dp[i-1][k]%mod*C(k,j)%mod*C(n-k,m-j))%mod; 73 dp[i][k-j+m-j]%=mod; 74  } 75  } 76  } 77  } 78 printf("%lld\n",dp[kk][n]); 79  } 80 return 0; 81 }