Codeforces #309 Div1 A. Kyoya and Colored Balls

この回Dが簡単だったため、ABCD解いてもレート減。
http://codeforces.com/contest/553/problem/A

問題

1～KのK種類の色のボールがそれぞれC[i]個ずつある。
これを順に並べる。

その際、i番の最後のボールの左側に、(i+1)番のボールが全部並ばないようにしたい。
そのような並べ方は何通りか。

解法

色の番号の少ない順に並びを決めていく。
i番目までのボールの並べ方をF(i)通りとし、S(i)=sum(C[1..i])とする。

(i+1)番目のボールの最後のボールは右端でないといけないので、で計算すればよい。

int K,C[1010];
ll mo=1000000007;

ll combi(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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	ll ret=1,T=0;
	FOR(i,K) {
		cin>>C[i];
		ret=ret*combi(T+C[i]-1,C[i]-1)%mo;
		T+=C[i];
	}
	cout<<ret<<endl;
	
}

まとめ

まだ簡単。