TopCoder SRM 519 Div1 Medium RequiredSubstrings

実装がめんどくさい問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=11514

問題

N個の単語word[i]が与えられる。
L文字の文字列のうち、word[i]をちょうどC個含むものの数を答えよ。

解法

N個のword[i]それぞれに状態遷移図を書き、N要素の状態をベクトルとして保持するだけ。
最終的にマッチまでたどり着いたものがC個であるようなベクトルをDPで数え上げればよい。

ll mo=1000000009;

ll stt[6][51][26];
map<ll,int> SI;
vector<ll> V;
int ST2[50001][26];
ll dpdp[51][50000];

void CreateSTT(int tar,string& pat) {
	int x,y,z,l;
	ZERO(stt[tar]);
	l=pat.size();
	FOR(x,l) {
		FOR(y,26) {
			if('a'+y == pat[x]) stt[tar][x][y]=x+1;
			else {
				string pre=pat.substr(0,x)+(char)('a'+y);
				for(z=1;z<=x;z++) if(pre.substr(pre.size()-z) == pat.substr(0,z)) stt[tar][x][y]=z;
			}
		}
	}
	FOR(y,26) stt[tar][l][y]=l;
}

class RequiredSubstrings {
	public:
	int solve(vector <string> words, int C, int L) {
		int i,x,y;
		vector<string> W;
		FOR(i,words.size()) if(words[i].size()<=L) W.push_back(words[i]);
		
		int N=W.size();
		FOR(i,N) CreateSTT(i,W[i]);
		
		ZERO(ST2);
		SI.clear();
		V.clear();
		queue<ll> Q;
		
		Q.push(0);
		V.push_back(0);
		SI[0]=0;
		
		while(!Q.empty()) {
			ll cur=Q.front();
			Q.pop();
			
			FOR(i,26) {
				ll ne=0;
				FOR(x,N) ne |= stt[x][(cur>>(6*x))&63][i]<<(6*x);
				if(SI.find(ne)==SI.end()) SI[ne]=SI.size()-1, Q.push(ne), V.push_back(ne);
				ST2[SI[cur]][i]=SI[ne];
			}
		}
		
		ZERO(dpdp);
		dpdp[0][0]=1;
		FOR(i,L) {
			FOR(x,V.size()) {
				FOR(y,26) dpdp[i+1][ST2[x][y]] = (dpdp[i+1][ST2[x][y]]+dpdp[i][x])%mo;
			}
		}
		
		ll ret=0;
		FOR(x,V.size()) {
			int num=0;
			FOR(y,N) if(((V[x]>>(6*y))&63)==W[y].size()) num++;
			if(num==C) ret+=dpdp[L][x];
		}
		
		return ret%mo;
	}
};

まとめ

こういう力技っぽいの、Div1 MediumよりDiv2 Hardっぽい。