CF 111D - Petya and Coloring - c++编程基础

题目大意：

用k种颜色涂 n*m 的矩形，要求如果 1~i 和 i+1~m 所用的颜色种类一样多，不要求颜色一样、

思路：

可以推出第一列和第m列所用的颜色数量是一样的。

证明：如果a[1~1]=i a[m~m]=j (i 那么a[1~1]=i

然后中间的m-2列是不能出现新颜色的。也就是必须是第一列和第m列的颜色不然会导致两边不相等了。

用dp[i] 表示用i种颜色且必须是i种颜色涂在n个格子上的方式。

那么 dp[i] = i^n-segma(C(i,j)*dp[j]) 1<=j

然后我们开始处理，

当m==1的时候就是k^n

当m==2的时候左边i种右边 i种就是（C（k，i）*dp[i]）^2...

当m==3的时候

要枚举相同的颜色的数量i 和不同的颜色的数量j

第一列在k个里选i个然后在k-i个里选择选择j个第m列则要在k-i-j里再选j个

然后再涂上去就是乘以 dp[i+j]...

#include #include #include #include typedef long long LL; using namespace std; const LL mod=1000000007; LL fac[1000005]={1},rev[1000005]={1}; LL dp[1005]; LL pow_mod(LL a,LL i,LL n) { if(i==0)return 1%n; LL temp=pow_mod(a,i>>1,n); temp=temp*temp%n; if(i&1)temp=temp*a%n; return temp; } void init() { for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod,rev[i]=pow_mod(fac[i],mod-2,mod); } LL C(int n,int m) { return (fac[n]*rev[m]%mod)*rev[n-m]%mod; } int main() { init(); int n,m,k; scanf("%d%d%d",&n,&m,&k); if(m==1) { printf("%I64d\n",pow_mod(k,n,mod)); return 0; } for(int i=1;i<=n && i<=k;i++) { dp[i]=pow_mod(i,n,mod); for(int j=1;j