Typical DP Contest O - 文字列

問題

英小文字からなる文字列で、
aをちょうどfreq[1]個
bをちょうどfreq[2]個…
zをちょうどfreq[26]個含み、同じ文字が隣り合わないものはいくつあるか、
mod 10^9 + 7で求めよ。

制約条件

freq[i]≦10

方針

freqが0の文字はないものとして考えてよい。（最初に消しておけばよい）

dp[何種類目まで文字を使ったか][同じ文字が何回隣り合っているか] := 場合の数
を更新するようなDPをすればよい。

一つの状態から次の文字を使うときの遷移は、

• 同じ文字が隣り合っている場所を何箇所使うか
• 違う文字が隣り合っている場所を何箇所使うか

を決めれば定まる。

上二つを決めたとき、次に同じ文字が何回隣り合っているかは、

• 文字を何個に分割するかをk個とすると、a[i] - k個だけ増える
• 同じ文字が隣り合っていた場所のうち、新しく挿入する場所をl個とすると、l個だけ減る

の式で一つに定まる。

これを、あとは各遷移が何通りあるかを掛ければよい。
同じ文字が隣り合っている場所の選び方はC[同じ文字隣り合う個数][使う場所個数]
違う文字が隣り合っている場所の選び方はC[違う文字隣り合う個数][使う場所個数]
各場所ごとに1文字消費するので、残りの文字の入れ方が、
H[残り文字数][使う場所]
となってこれらの積。

ソースコード

const int mod = inf + 7;
int n, a[30], s[30];
int dp[30][300], C[600][600];

int main(){
	
	rep(i, 600) rep(j, i+1) C[i][j] = j==i||j==0 ? 1 : (C[i-1][j-1] + C[i-1][j]) % mod;
	
	rep(i, 26){
		int x;
		cin >> x;
		if(!x) continue;
		a[n] = x;
		s[n + 1] = s[n] + x;
		n++;
	}
	
	dp[0][0] = 1;
	
	rep(i, n) rep(bad, 10 * i + 1) if(dp[i][bad]){
		
		int good = s[i] + 1 - bad;
		//goodが違う文字同士が隣り合う回数
		//badが同じ文字同士が隣り合う回数
		
		rep(usegood, good + 1) rep(usebad, bad + 1){
			
			if(!usegood && !usebad) continue;
			if(a[i] - usegood - usebad < 0) continue;
			if(bad - usebad + a[i] - usegood - usebad < 0) continue;
			
			int way = (ll)dp[i][bad] * C[good][usegood] % mod
			* C[bad][usebad] % mod
			* C[a[i] - 1][usegood + usebad - 1] % mod; 
			//個数の振り分け方。usegood + usebad個は自動で決まるので、残りの振り分け方。
			//a[i] - usegood - usebad個を、usegood + usebad個の箱に重複を許して入れる場合の数。
			//H[a[i] - usegood - usebad][usegood + usebad]
			// = C[a[i] - 1][usegood + usebad - 1]
			
			(dp[i + 1][bad - usebad + a[i] - usegood - usebad] += way) %= mod;
		}
	}
	cout << dp[n][0] << endl;
	
	return 0;
}