要求一条直线分割矩阵时左右颜色数一样，那么就说明一个问题。
直线左右移动时是不会改变左右矩阵的颜色集合的。
所以说明：2~m-1列的颜色集一定属于第一列与第m列颜色集的交集。
而且第一列与第m列颜色集大小相等。
显然需要预处理n个点m种颜色的方案数，设为$g(i,j)$
这样，只需要确定第一列和最后一列颜色集，假设交集是$i$种颜色，
就可以算出中间的颜色方案数：$i^{n*(m-2)}$
假设两边颜色个数都是$j$（$j\ge i$）那么两边颜色的答案（$(g(n,j)j!)^2$）
这$i$种颜色共有$C_k^i$种选法，两边各$j$种颜色，且只有$i$种颜色相同的方案就是：
$\Large C_k^iC_{k-i}^{2(j-i)}C_{2(j-i)}^{j-i}$
那么答案就是
$\Large\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}C_k^iC_{k-i}^{2(j-i)}C_{2(j-i)}^{j-i}{(g(n,j)j!)^2}{i^{n(m-2)}}$
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 typedef long long lnt; 5 const lnt mod=1000000007; 6 lnt g[1010][1010]; 7 lnt fac[1000010]; 8 lnt inv[1000010]; 9 int n,m,k; 10 lnt ans; 11 lnt ksm(lnt a,lnt b) 12 { 13 lnt ans=1; 14 while(b) 15 { 16 if(b&1)ans=ans*a%mod; 17 a=a*a%mod; 18 b=b/2; 19 } 20 return ans; 21 } 22 lnt C(int x,int y) 23 { 24 if(y>x)return 0; 25 return fac[x]*inv[y]%mod*inv[x-y]%mod; 26 } 27 lnt squ(lnt x) 28 { 29 return x*x%mod; 30 } 31 int main() 32 { 33 g[0][0]=1; 34 fac[0]=inv[0]=fac[1]=inv[1]=1; 35 for(int i=2;i<=1000000;i++) 36 { 37 fac[i]=(fac[i-1]*i)%mod; 38 inv[i]=(mod-mod/i)*inv[mod%i]%mod; 39 } 40 for(int i=1;i<=1000000;i++)inv[i]=inv[i]*inv[i-1]%mod; 41 scanf("%d%d%d",&n,&m,&k); 42 if(m==1) 43 { 44 printf("%I64d\n",ksm(k,n)); 45 return 0; 46 } 47 for(int i=1;i<=n;i++) 48 { 49 for(int j=1;j<=i&&j<=k;j++) 50 { 51 g[i][j]=(g[i-1][j-1]+g[i-1][j]*j)%mod; 52 } 53 } 54 for(int i=0;i<=n;i++) 55 { 56 lnt tmp=ksm(i,n*(m-2))*C(k,i)%mod; 57 for(int j=i;j<=n;j++) 58 { 59 ans=(ans+tmp*C(k-i,(j-i)*2)%mod*C((j-i)*2,j-i)%mod*squ(g[n][j]*fac[j]%mod)%mod)%mod; 60 } 61 } 62 printf("%I64d\n",(ans%mod+mod)%mod); 63 return 0; 64 }
codeforces111D. Petya and Coloring(组合数学，计数问题)
原文：https://www.cnblogs.com/blog-Dr-J/p/10389476.html