P2182翻硬币（题解）
Leap_Frog
·
·
题解
Problem.
刚开始有一个长度为N的硬币状态。
求每次翻M次后变成结束状态的方案数。
Solution.
首先，我们考虑dp。
我们观察题目，发现有一个性质：
硬币所在的位置并不影响硬币的翻转！
所以我们并不需要记录每枚硬币具体位置和状态，
只需要记录有几枚硬币朝上就可以表示一个状态了。
当然，由于结束状态不好表示，可以先把初始状态先全都异或上结束状态。
相当于可以记录还有多少枚硬币和结束状态不相同。
则起始状态为：$dp[0][dif]=1$，其他都为$0$（dif表示起始状态和结束状态差别的硬币数。
$dp[i][j]$可以从$dp[i-1][?]$转移过来。
我们可以枚举选的$M$枚硬币中有多少枚和结束状态不相同。
~~虵~~设我们选了$l$枚与结束状态不相同的硬币，那么就有$M-l$枚硬币和结束状态相同。
那么少了$l$枚的与硬币与结束状态不相同的硬币，多了$M-l$枚与结束状态不相同的硬币。（对不起，这里有点绕，笔者要慢慢写，才能把笔者绕清楚
那么也就是多了$M-l\times2$枚与结束状态不相同的硬币。
那么$dp[i][j+M-l\times2]$是从$dp[i-1][j]$转移过来的。
此时相当于在$j$枚与结束状态不同的硬币中选出了要翻转的$l$枚和结束状态不相同的硬币，
以及在$N-j$枚与结束状态相同的硬币中选出要反转的$M-l$枚和结束状态相同的硬币。
所以这一步的方案数是$C_j^l\times C_{N-j}^{M-l}$。
所以
$$dp[i][j+M-l\times2]=\sum_{l=1}^{M\&0\leq j+M-l\times2\leq N}dp[i][j]\times C_j^l\times C_{N-j}^{M-l}$$
~~终于推出来了，能去写代码了~~
~~没错，您没听错，我这个菜逼先写题解后写代码的！~~
### Coding.
```cpp
#include<bits/stdc++.h>//万能头
using namespace std;//不解释
const int N=105,P=1000000007;//N范围，P是模数
int n,k,m,dif,a[N],dp[N][N],c[N][N];
//n,k,m都是题目中的，dif是Solution.中的dif，dp是dp数组
//c是组合数，a是暂时存储起始状态的数组
int main()
{
scanf("%d%d%d",&n,&k,&m),dif=0;//读入，把dif清零
for(int i=1;i<=n;i++) scanf("%1d",a+i);//读入起始状态
for(int i=1,x;i<=n;i++) scanf("%1d",&x),dif+=(a[i]^x);//求出起始状态与终止状态差的硬币数
memset(dp,0,sizeof(dp)),dp[0][dif]=1,memset(c,0,sizeof(c));//初始化，具体见Solution.
for(int i=0;i<=n;i++) c[i][0]=1;//初始化求组合数
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;//求组合数
for(int i=1;i<=k;i++)
for(int j=0;j<=n;j++)//枚举dp[i][j]
for(int l=0;l<=m;l++)//枚举l
if(j-(l<<1)+m>=0&&j-(l<<1)+m<=n)//检查l的范围
dp[i][j-(l<<1)+m]=(dp[i][j-(l<<1)+m]+1ll*dp[i-1][j]*c[j][l]%P*c[n-j][m-l]%P)%P;//dp转移
return printf("%d\n",dp[k][0]),0;//输出答案并结束
}
```