TopCoder SRM 599 Div2 Hard SimilarNames2

あれ、950ptとはいえMediumよりこちらの方がすんなり行った。
http://community.topcoder.com/stat?c=problem_statement&pm=12871

問題

distinctな文字列がN個与えられる。
数Lが与えられたとき、以下を満たす文字列の並び方の数を答えよ。

• 先頭のL個について、i番目はi+1番目の文字列のprefixである。

解法

まず、N個の各文字列間で、互いがprefixになりうるかを判定する。
次に、状態として[順番][最後の要素]を持ち、i番目の要素の次はi番目をprefixとできる(i+1)を持ってくる、というDPを先頭L個分実行する。この処理はO(LN^2)。
最後に残り(N-L)個を適当に並べるので(N-L)!を掛ければよい。

int mat[51][51];
ll mo=1000000007;
ll dpdp[51][51];

class SimilarNames2 {
	public:
	int count(vector <string> names, int L) {
		int x,y,z,N,i;
		N=names.size();
		FOR(x,N) FOR(y,N) mat[x][y]=(x!=y && names[y].size()>names[x].size() && names[y].find(names[x])==0);
		ZERO(dpdp);
		FOR(x,N) dpdp[1][x]=1;
		for(x=2;x<=L;x++) {
			FOR(y,N) FOR(z,N) if(mat[y][z] && dpdp[x-1][y]) dpdp[x][z] = (dpdp[x][z] + dpdp[x-1][y])%mo;
		}
		
		ll ret=0;
		FOR(x,N) ret+=dpdp[L][x];
		ret %= mo;
		FOR(i,N-L) ret=(ret*(i+1))%mo;
		
		return ret;
		
	}
};

まとめ

distinctの縛りを外して、同じ要素があった方が面白い問題だったんじゃないのかなぁ。
O(LN^3)だからどのみち間に合うし。