TopCoder SRM 586 Div2 Hard StringWeightDiv2

今回のDiv2 HardはDiv1 Hardの制限を緩めたもの。
http://community.topcoder.com/stat?c=problem_statement&pm=12695

問題

A-Zの26文字から構築される文字列のweightを以下の様に定義する。

• 各文字が最初に出てくる位置と最後に出てくる位置の差分を、文字ごとに累積したもの

文字列長Lに対してlightな文字列とは、そのweightが同じ文字列長で実現できる最小weightと一致することを示す。
Lが与えられたとき、lightな文字列の組み合わせ数を返せ。

解法

L<=26の時、L個の異なる文字を使えばweightが0になる。組み合わせは。

L>27の時、26個の文字を全部使う。また、各文字は連続している必要がある。
各文字が１個以上使われていれば、各文字の数は問わない。
例えばAAABBとAABBBはどちらもweight=3で同じ。

よって、26文字の並べ方26!通りと、L個の文字を26個のアルファベットに最低１個ずつ振り分ける方法を掛ければよい。

ll mo=1000000009;
ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	return C_[P_][Q_];
}

class StringWeightDiv2 {
	public:
	int countMinimums(int L) {
		int i;
		
		ll r=1;
		if(L<=26) {
			FOR(i,L) r=(r*(26-i))%mo;
		}
		else {
			r=comb(L-1,25);
			FOR(i,26) r=(r*(26-i))%mo;
		}
		return (int)r;
	}
};

まとめ

最初、最後の組み合わせ数の計算はかと思ったけどなのね。