题解 P2182 【翻硬币】

· · 题解

本蒟蒻默默来水一发题解。。

话说回来真的有必要吐槽一句，取模的优先级好低啊，一开始一直没有加足够的括号导致有七个点一直爆炸，最后在每个取模的地方都加了括号，终于过了~

另外数组是要开long long的，应该不会有人像我一样傻吧。

说思路：

此题很明显的DP，状压DP，但计算一下纯打状压DP的话时间复杂度会炸的，同时我们能够发现，其实翻哪里的硬币是不重要的，重要的是最后是不是翻成了原来的样子，于是三重循环——

第一重枚举翻的次数

第二重枚举当前状态与目标状态不同硬币的个数

第三重枚举要翻转的与目标状态不同的硬币的个数

【话说刚开始写成了相同的，然后一直炸】

dp[i][j]表示翻转i次，还有j个与目标状态不同位置的方案数

方程就很好想啦，详见代码~

另外，由于本蒟蒻是刚做完组合数问题然后做这道，自然第一反应就是杨辉三角组合数问题。于是对于枚举的状态，从相同的里面挑需要翻的数量、从不同的里面挑需要翻的数量，然后应用乘法原理乘起来得出方案数【一定要加括号取模！】

最后输出结果就好啦

然后上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 1000000007
using namespace std;
int n,k,m,tot;
char a[201],b[201];
long long sum[201][201],dp[201][201];
int main(){
    scanf("%d%d%d",&n,&k,&m);
    scanf("%s%s",a+1,b+1);//刚刚学会的直接从1位置开始读字符串 
    //for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    //for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++)
     if (a[i]!=b[i]) tot++;
    for (int i=0;i<=max(n,m);i++) sum[i][0]=sum[i][i]=1;
    for (int i=1;i<=n;i++)
     for (int j=1;j<=m;j++)
      sum[i][j]=(sum[i-1][j]+sum[i-1][j-1])%mo;
    //杨辉三角的问题 
    dp[0][tot]=1;//对于开始状态的初始化 
    for (int i=1;i<=k;i++)//i枚举翻转的次数 
     for (int j=0;j<=n;j++)//j枚举当前状态与目标状态不同硬币的个数 
      for (int r=0;r<=min(j,m);r++){//r枚举要翻转的与目标状态不同的硬币的个数 
          if (j-2*r+m>=0&&j-2*r+m<=n){//j-2*r+m表示除了翻转后剩下的不同于目标状态的硬币的个数 
              dp[i][j-2*r+m]=(dp[i][j-2*r+m]%mo+((dp[i-1][j]*((sum[n-j][m-r]*sum[j][r])%mo))%mo))%mo;
              //应用乘法原理进行方案数的求解，相邻两项之间的连接用乘不用加 
          }
         }
    printf("%lld",dp[k][0]);
    return 0;
}
代码略丑\(-.-)/不喜勿喷