题目概述

用 $K$ 种颜色对 $n\times m$ 的网格进行染色，需要保证无论怎么样纵切将棋盘分为左右两个部分， 两个部分的颜色种类数都必须相等，求方案数。

解题报告

在NOIP前，这道题被法老当做NOIP题出进了模拟赛……

考虑第一列有 $a$ 种颜色，那么 $[2,m]$ 列也有 $a$ 种颜色，再考虑前两列有 $x(x\ge a)$ 种颜色，那么 $[3,m]$ 列也有 $x(x\le a)$ 种颜色，所以 $x=a$ ，以此类推所有格子只有 $a$ 种颜色，反过来考虑同理。

因此我们可以枚举 $a$ 表示第一列和第 $n$ 列有 $a$ 种颜色，那么中间 $m-2$ 列只能使用第一列和第 $n$ 列颜色的交集，假设有 $b$ 种颜色，则方案数为：

$$ \sum_{a=1}^{min\{n,K\}}\sum_{b=0}^{a}{K\choose a}{K-a\choose a-b}{a\choose b}b^{n(m-2)}[S(n,a)a!]^2 $$

前面一堆就表示选出 $a$ 种颜色，$b$ 种交集，中间用 $b$ 种颜色的方案数，后面那个 $S(n,a)$ 表示第二类斯特林数，$[S(n,a)a!]^2$ 表示第一列和第 $n$ 列涂上 $a$ 种颜色的方案数。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000,maxk=1000000,MOD=1000000007;

int te,n,m,K,fac[maxk+5],INV[maxk+5],S[maxn+5][maxn+5],ans;

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    INV[0]=INV[1]=1;for (int i=2;i<=maxk;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=maxk;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    S[0][0]=1;for (int i=1;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=(S[i-1][j-1]+(LL)S[i-1][j]*j%MOD)%MOD;
    for (int i=0;i<=maxn;i++) for (int j=1;j<=i;j++) S[i][j]=Pow((LL)S[i][j]*fac[j]%MOD,2);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);ans=0;if (m==1) {printf("%d\n",Pow(K,n));continue;}
        for (int i=1;i<=n&&i<=K;i++)
            for (int j=0;j<=i;j++)
                ans=(ans+(LL)C(K,i)*C(K-i,i-j)%MOD*C(i,j)%MOD*Pow(j,n*(m-2))%MOD*S[n][i]%MOD)%MOD;
        printf("%d\n",ans);
    }return 0;
}