Codeforces #589 Div2 E. Another Filling the Grid

なんかこの問題えらくあっさり解いてるな。
https://codeforces.com/contest/1228/problem/E

問題

正整数N,Kが与えられる。
以下のようにN*Nのグリッドに数字を埋める埋め方を求めよ。

• 各セルの数字は1～Kのいずれかの整数とする。
• 各列1つは1の書かれたセルがある。
• 各行1つは1の書かれたセルがある。

解法

f(r,c) := 先頭r行目までを考えたとき、c列だけ1のすでに設定された列がある場合の数字の埋め方
とする。r+1行目を考えたとき、1列以上1を埋めないといけないわけだが、すでに1があるc列または残りの(N-c)列から1個以上選ぶ選び方を数え上げ、残りの列には1以外を埋めるようにしていけばよい。

int N,K;
ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll from[251],to[251];
ll pk[252],pk1[252];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	from[0]=1;
	
	pk[0]=pk1[0]=1;
	FOR(i,251) pk[i+1]=pk[i]*K%mo,pk1[i+1]=pk1[i]*(K-1)%mo;
	
	FOR(y,N) {
		ZERO(to);
		for(x=0;x<=N;x++) for(r=0;x+r<=N;r++) {
			if(r==0) {
				(to[x]+=from[x]*pk1[N-x]%mo*(pk[x]+mo-pk1[x]))%=mo;
			}
			else {
				(to[x+r]+=from[x]*comb(N-x,r)%mo*pk1[N-x-r]%mo*pk[x])%=mo;
			}
		}
		swap(from,to);
	}
	cout<<from[N]<<endl;
	
}

まとめ

2000ptでもいい気はする。