TopCoder SRM 849 : Div1 Medium ColorfulTrees

気付いてしまうとだいぶ楽。
https://community.topcoder.com/stat?c=problem_statement&pm=18101

問題

正整数N,Cが与えられる。

num(T,C)は以下を表すとする。

• N頂点の木Tの各頂点をC色で塗る。隣接点は異なる色となるようにし、かつC色はいずれも1頂点以上存在するようにしたい。
• そのような塗り分けは何通りか。

Tに任意のN頂点の木を取れるとき、num(T,C)の最小値と最大値を求めよ。

解法

まず、Tの形状は関係ない。
根付き木を考えると、隣接点の条件を「親と異なる色とする」と読み替えると、彩色パターンはC*(C-1)^(N-1)通りで固定である。
あとは、C色が1頂点以上存在する条件は、包除原理で解ける。

結局で良い。

const 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_=1400001;
	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 dp[1010101];

class ColorfulTrees {
	public:
	vector <int> count(int N, int C) {
		if(C>N) return {0,0};
		int i;
		ll ret=0;
		for(i=1;i<=C;i++) {
			dp[i]=i*modpow(i-1,N-1)%mo;
			if((C-i)%2) {
				ret+=mo-dp[i]*comb(C,i)%mo;
			}
			else {
				ret+=dp[i]*comb(C,i)%mo;
			}
		}
		ret=(ret%mo+mo)%mo;
		
		
		return {(int)ret,(int)ret};
		
	}
}

まとめ

minとmaxが一緒と気づくまでにちょっと時間かかってしまった。