Codeforces #258 Div2 E. Devu and Flowers

うーむ、これはわからんかった。
http://codeforces.com/contest/451/problem/E

問題

N種類の花がそれぞれF[i]本ずつある。
同じ種類の花はそれぞれ見分けがつかない。

花を合計S本選ぶ選び方は何通りあるか。

解法

F[i]やSが小さければ典型的なDP問題だが、F[i]やSが大きいのでそうはいかない。
一方Nはかなり小さいのでそれで何とかしたい。

Editorialは無駄にトリッキーなので、Editorialのコメント欄を参考に回答。

各花の選び方を考える際、上限F[i]を無視すると、S本をN種類から選ぶのは単純な重複組み合わせなのでで求められる。
ここから包除原理を使い、各種類の花がF[i]を超えるケースを除いていけばよい。

各花の種類がF[i]を超えるかどうかをbitmaskで管理し、総当たりする。
bitmaskで超えると判定される種類は最低(F[i]+1)本の花を含むので、その分Sから(F[i]+1)を引いていく。
最終的に残った値をS'とすると、をbitmask1の1が立ったbit数で符号反転したものを足しこんでいけばよい。

int N;
ll S,F[30];
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	int i;
	const int num=100;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[mo%i]*(mo-mo/i)%mo;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%mo;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * ((N_-i)%mo))%mo;
	return ret;
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>S;
	FOR(i,N) cin>>F[i];
	ll ret=0;
	int mask;
	FOR(mask,1<<N) {
		ll tot=S;
		int bc=__builtin_popcount(mask);
		FOR(i,N) if(mask&(1<<i)) tot-=F[i]+1;
		if(tot<0) continue;
		
		ll val=combi(tot+N-1,N-1);
		if(bc%2) val=mo-val;
		ret+=val;
		
	}
	cout << ret%mo << endl;
}

まとめ

Editorialのトリッキーさもコメント欄の解法も参考になった。