Flipping Game 题解(dp)

题目链接

题目思路

这个\(dp\)比较巧妙

设\(dp[i][j]\)表示在第\(i\)次操作后，还有\(j\)个数不一样的答案

那么最后输出\(dp[k][0]\)

转移方程即每次枚举选了s个与最终态不同的灯，m-s个与最终态相同的灯操作

那么\(dp\)方程即为

$ dp[i+1][j-s+m-s]=dp[i+1][j-s+m-s]+dp[i][j]c(j,s)c(n-j,m-s);$

代码

#include
#define fi first
#define se second
#define debug cout<<"I AM HERE"<>1;
    }
    return ans;
}
void init(int n){
    fac[0]=finv[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    finv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=1;i--){
        finv[i]=finv[i+1]*(i+1)%mod;
    }
}
ll c(ll a,ll b){
    if(an) continue;
                    dp[i+1][j-s+m-s]=(dp[i+1][j-s+m-s]+dp[i][j]*c(j,s)%mod*c(n-j,m-s)%mod)%mod;
                }
            }
        }
        printf("%lld\n",dp[k][0]);
    }
    return 0;
}