Codeforces 111 D. Petya and Coloring

問題

nxmマスのタイルをk色を使って塗る。
ただし以下の条件が満たされなければならない。

  • どのような縦の直線にそってマスを(空でない)二つに分割したときも、両方で使われている色の数が等しい。


条件を満たすタイルの塗り方は何通りか、mod 10^9+7で求めよ。

制約条件

n,m≦1000
k≦10^6

方針

左端の列と右端の列で使われている色の数は等しくないと矛盾する。
左端の列と右端の列で共通する色をa色とする。
全体でb色の色が使われているとする。


左端と右端以外の列では全てのタイルがa色のどれかのタイルで塗られているはずである。
なので、それぞれのa,bについての場合の数を求めて足し合わせればいい。


色の決め方がC(k,a)*C(k-a,b-a)*C(k-b,b-a)通りあって、
両端以外の列の塗り方がa^(n*(m-2))通り、
両端の色の塗り方はn個のタイルをb色に(ただし割り当てられない色があってはダメ)割り当てる場合の数。


最後のやつは、区別するm人を区別するr個の部屋に空室がないように割り当てる場合の数で、
これはf(m,r)とおくと、f(m,r)=r*(f(m-1,r-1)+f(m-1,r))の漸化式が成り立つのでDPで求まる。


全部かけて足せばいい。

ソースコード

const int mod=(int)1e9+7;
int n,m,k;
int dp[1001][1001];

inline int pow(int n,int m){
	int res=1;
	for(;m;m>>=1){
		if(m&1)res=(ll)res*n%mod;
		n=(ll)n*n%mod;
	}
	return res;
}
int room(int m,int r){
	int &res=dp[m][r];
	if(res>=0)return res;
	if(m==0||r==0)return m==0&&r==0;
	return res=(ll)r*(room(m-1,r-1)+room(m-1,r))%mod;
}
int fact[1000001];
int extgcd(int a,int b,int &x,int &y){
	int d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else x=1, y=0;
	return d;
}
int inv(int n){
	int x,y;
	extgcd(n,mod,x,y);
	return (x%mod+mod)%mod;
}
int C(int n,int k){
	return (ll)fact[n]*inv(fact[n-k])%mod*inv(fact[k])%mod;
}
void run()
{
	cin>>n>>m>>k;
	if(m==1){
		cout<<pow(k,n)<<endl;
		return;
	}
	memset(dp,-1,sizeof(dp));
	fact[0]=1;
	rep(i,1000000)fact[i+1]=fact[i]*(i+1ll)%mod;
	
	int ans=0;
	for(int a=0;a<=min(n,k);a++)for(int b=max(1,a);b<=n&&2*b-a<=k;b++){
		ll tmp=(ll)C(k,a)*C(k-a,b-a)%mod*C(k-b,b-a)%mod;
		tmp=tmp*room(n,b)%mod*room(n,b)%mod;
		tmp=tmp*pow(a,n*(m-2))%mod;
		ans=(ans+tmp)%mod;
	}
	cout<<ans<<endl;
}