[51NOD1604]对称的方格颜色

2019-11-08 18:42:54

字体：大中小

来源：转载

供稿：网友

题目大意

用K $K$ 种颜色对一个n×m $n/times m$ 的矩形板染色。对于任意一条竖直的线，都能把矩形分成不为空的两个部分（注意这里是分隔是沿着两列的交界分隔），要求染色方案满足每部分中的不同颜色种数要相同。答案对109+7 $10^9+7$ 取模。

1≤n≤1000,2≤m≤1000,1≤K≤106 $1/le n/le1000,2/le m/le1000,1/le K/le10^6$

题目分析

这题刚开始看似乎无从下手，我们要找到一个比较好的突破口来做题。考虑最左边和最右边两列，它们具有一定的特殊性质。先考虑最左边一列，可以发现除了最右边一列，每一列的出现过的颜色都一定在第一列中出现过，这个可以使用反证法来证明：如果存在一种颜色是第一列没有出现过的，并且假设其左边的列都是第一列有的颜色，那么从这一列右边切开，右边部分的颜色种类数就是第一列的颜色种类数加一，然后我们从这一列左边切开，可以发现右边部分的颜色种类数显然和左边不一样。同理我们可以证明除了最左边一列，每一列出现过的颜色都一定在最后一列出现过。的确，第一列和最后一列的颜色种类不一定完全相同，中间的列的颜色一定属于这两列颜色种类的交集。那么第一列和最后一列的颜色种类数是否相等呢？答案是肯定的。那么正解就很显然了，我们令fi,j $f_{i,j}$ 表示i $i$ 个格子填j $j$ 种颜色的方案数，枚举a $a$ 为第一列的颜色种类数，b $b$ 为第一列和最后一列共有的颜色数，那么答案就是 ∑a∑b(K2a−b)(2a−bb)(2(a−b)a−b)(fn,aa!)2bn(m−2) $/sum_a/sum_b{K/choose2a-b}{2a-b/choose b}{2(a-b)/choose a-b}/left(f_{n,a}a!/right)^2b^{n(m-2)}$ 时间复杂度O(n2) $/mathrm O(n^2)$ 。

代码实现

#include <iostream>#include <cstdio>using namespace std;const int P=1000000007;const int MAXK=1000005;const int N=1005;int fact[MAXK],invf[MAXK];int f[N][N];int n,m,K,ans;int sqr(int x){return 1ll*x*x%P;}int C(int n,int m){return n<m?0:1ll*fact[n]*invf[m]%P*invf[n-m]%P;}int quick_power(int x,int y){ int ret=1; for (;y;x=1ll*x*x%P,y>>=1) if (y&1) ret=1ll*ret*x%P; return ret;}void PRe(){ fact[0]=1; for (int i=1;i<=K;++i) fact[i]=1ll*fact[i-1]*i%P; invf[K]=quick_power(fact[K],P-2); for (int i=K;i>=1;--i) invf[i-1]=1ll*invf[i]*i%P; f[1][1]=1; for (int i=2;i<=n;++i) for (int j=1;j<=i;++j) f[i][j]=(1ll*f[i-1][j]*j%P+f[i-1][j-1])%P;}void calc(){ ans=0; for (int b=0;b<=n;++b) { int t=quick_power(b,n*(m-2)); for (int a=min(K+b>>1,n);a>=b&&a>=1;--a) (ans+=1ll*C(K,2*a-b)*C(2*a-b,b)%P*C(2*(a-b),a-b)%P*sqr(1ll*f[n][a]*fact[a]%P)%P*t%P)%=P; }}int main(){ freopen("color.in","r",stdin),freopen("color.out","w",stdout); scanf("%d%d%d",&n,&m,&K); pre(),calc(); printf("%d/n",ans); fclose(stdin),fclose(stdout); return 0;}

上一篇：xprintf format string

下一篇：POJ - 1936 All in All解题报告