AtCoder Beginner Contest 167 E：Colorful Blocks 组合数/DP分析
我们先DP分析
dp[i][j]表示，按从左往右的顺序填到i时，有j对相邻数字不同，的方案数
显然：dp[i][j]=dp[i-1][j]*(m-1)+dp[i-1][j-1];
我们把DP在纸上推演如下：
发现：每个i所在行的d[pi][j]其实就是二次项展开的一项
求和dp[n][0]到dp[n][k]即可。
第二种思路是用组合数直接进行分析：
考虑：n个数，k个相邻位置数相同，
我们在n-1个空位中选择k个位置，使得k左右数相同。
然后固定最左边的数，有m种选法，依次往右选，遇到刚才选出的位置，选法只有一种。
其余都是m-1种选法。
综上方案数为：
同样求和即可。
#include
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<>n>>m>>k;
fac[0]=p[0]=inv[0]=1;
for(int i=1;i<=200000;i++)fac[i]=fac[i-1]*i%mod,p[i]=p[i-1]*(m-1)%mod;;
inv[200000]=qpow(fac[200000],mod-2);
for(int i=200000-1;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
ll ans=0;
for(int i=1;i<=k;i++)
{
ll C=fac[n-1]*inv[i]%mod*inv[n-1-i]%mod;
ans=(ans+m*p[n-i-1]%mod*C%mod)%mod;
}
ans=(ans+m*p[n-1]%mod)%mod;
cout<<ans<<endl;
return 0;
}
夕林山寸
原创文章 410获赞 22访问量 2万+
关注
私信
展开阅读全文
作者：夕林山寸
