96b8b260e1 2011-09-20        kinaba: #include <iostream>
96b8b260e1 2011-09-20        kinaba: #include <sstream>
96b8b260e1 2011-09-20        kinaba: #include <iomanip>
96b8b260e1 2011-09-20        kinaba: #include <vector>
96b8b260e1 2011-09-20        kinaba: #include <string>
96b8b260e1 2011-09-20        kinaba: #include <map>
96b8b260e1 2011-09-20        kinaba: #include <set>
96b8b260e1 2011-09-20        kinaba: #include <algorithm>
96b8b260e1 2011-09-20        kinaba: #include <numeric>
96b8b260e1 2011-09-20        kinaba: #include <iterator>
96b8b260e1 2011-09-20        kinaba: #include <functional>
96b8b260e1 2011-09-20        kinaba: #include <complex>
96b8b260e1 2011-09-20        kinaba: #include <queue>
96b8b260e1 2011-09-20        kinaba: #include <stack>
96b8b260e1 2011-09-20        kinaba: #include <cmath>
96b8b260e1 2011-09-20        kinaba: #include <cassert>
96b8b260e1 2011-09-20        kinaba: #include <cstring>
96b8b260e1 2011-09-20        kinaba: using namespace std;
96b8b260e1 2011-09-20        kinaba: typedef long long LL;
96b8b260e1 2011-09-20        kinaba: typedef complex<double> CMP;
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: template<int NC=26, char BC='a'>
96b8b260e1 2011-09-20        kinaba: struct AhoCorasick
96b8b260e1 2011-09-20        kinaba: {
96b8b260e1 2011-09-20        kinaba: 	AhoCorasick( const vector<string>& p ) : link(NC+1) {
96b8b260e1 2011-09-20        kinaba: 		// Create a trie
96b8b260e1 2011-09-20        kinaba: 		for(int i=0; i<p.size(); ++i) {
96b8b260e1 2011-09-20        kinaba: 			AhoCorasick* t = this;
96b8b260e1 2011-09-20        kinaba: 			for(int k=0; k<p[i].size(); t=t->link[p[i][k++]-BC])
96b8b260e1 2011-09-20        kinaba: 				if(!t->link[p[i][k]-BC])
96b8b260e1 2011-09-20        kinaba: 					t->link[p[i][k]-BC]=new AhoCorasick;
96b8b260e1 2011-09-20        kinaba: 			t->final.insert(i);
96b8b260e1 2011-09-20        kinaba: 		}
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: 		// Do BFS and draw failure links, and prepare for substring pattern
96b8b260e1 2011-09-20        kinaba: 		queue<AhoCorasick*> Q;
96b8b260e1 2011-09-20        kinaba: 		for(int c=0; c<NC; ++c)
96b8b260e1 2011-09-20        kinaba: 			if( link[c] ) {
96b8b260e1 2011-09-20        kinaba: 				Q.push(link[c]);
96b8b260e1 2011-09-20        kinaba: 				link[c]->link[NC] = this; // "c"'s suffix is ""
96b8b260e1 2011-09-20        kinaba: 				link[c]->final.insert(final.begin(), final.end());
96b8b260e1 2011-09-20        kinaba: 			}
96b8b260e1 2011-09-20        kinaba: 			else
96b8b260e1 2011-09-20        kinaba: 				link[c] = this;
96b8b260e1 2011-09-20        kinaba: 		while( !Q.empty() ) {
96b8b260e1 2011-09-20        kinaba: 			AhoCorasick* t=Q.front(); Q.pop();
96b8b260e1 2011-09-20        kinaba: 			for(int c=0; c<NC; ++c)
96b8b260e1 2011-09-20        kinaba: 				if( t->link[c] ) {
96b8b260e1 2011-09-20        kinaba: 					Q.push(t->link[c]);
96b8b260e1 2011-09-20        kinaba: 					AhoCorasick* r = t->link[NC]; // "r" is suffix of "t"...
96b8b260e1 2011-09-20        kinaba: 					while( !r->link[c] )
96b8b260e1 2011-09-20        kinaba: 						r = r->link[NC];
96b8b260e1 2011-09-20        kinaba: 					t->link[c]->link[NC] = r->link[c]; // then "rc" is suffix of "tc"
96b8b260e1 2011-09-20        kinaba: 					t->link[c]->final.insert(r->link[c]->final.begin(), r->link[c]->final.end());
96b8b260e1 2011-09-20        kinaba: 				}
96b8b260e1 2011-09-20        kinaba: 		}
96b8b260e1 2011-09-20        kinaba: 	}
96b8b260e1 2011-09-20        kinaba: 	const AhoCorasick* start() const { return this; }
96b8b260e1 2011-09-20        kinaba: 	const AhoCorasick* next(char c) const {
96b8b260e1 2011-09-20        kinaba: 		const AhoCorasick* t = this;
96b8b260e1 2011-09-20        kinaba: 		while( !t->link[c-BC] )
96b8b260e1 2011-09-20        kinaba: 			t = t->link[NC];
96b8b260e1 2011-09-20        kinaba: 		return t->link[c-BC];
96b8b260e1 2011-09-20        kinaba: 	}
96b8b260e1 2011-09-20        kinaba: 	const set<int>& accept() const { return final; }
96b8b260e1 2011-09-20        kinaba: 	~AhoCorasick() { for(int i=0; i<NC; ++i) if(link[i]!=this) delete link[i]; }
96b8b260e1 2011-09-20        kinaba: private:
96b8b260e1 2011-09-20        kinaba: 	AhoCorasick() : link(NC+1) {}
96b8b260e1 2011-09-20        kinaba: 	vector<AhoCorasick*> link;
96b8b260e1 2011-09-20        kinaba: 	set<int> final;
96b8b260e1 2011-09-20        kinaba: };
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: static const int MODVAL = 1000000009; // must be prime for op/
96b8b260e1 2011-09-20        kinaba: struct mint
96b8b260e1 2011-09-20        kinaba: {
96b8b260e1 2011-09-20        kinaba:   int val;
96b8b260e1 2011-09-20        kinaba:   mint():val(0){}
96b8b260e1 2011-09-20        kinaba:   mint(int x):val(x%MODVAL) {}
96b8b260e1 2011-09-20        kinaba: };
96b8b260e1 2011-09-20        kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: int bitcnt(LL x)
96b8b260e1 2011-09-20        kinaba: {
96b8b260e1 2011-09-20        kinaba: 	int c = 0;
96b8b260e1 2011-09-20        kinaba: 	for(; x; x>>=1)
96b8b260e1 2011-09-20        kinaba: 		c += x&1;
96b8b260e1 2011-09-20        kinaba: 	return c;
96b8b260e1 2011-09-20        kinaba: }
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: class RequiredSubstrings { public:
96b8b260e1 2011-09-20        kinaba:   int solve(vector <string> words, int C, int L)
96b8b260e1 2011-09-20        kinaba:   {
96b8b260e1 2011-09-20        kinaba:     AhoCorasick<> ac(words);
96b8b260e1 2011-09-20        kinaba:     return rec(L, C, 0, ac.start()).val;
96b8b260e1 2011-09-20        kinaba:   }
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba:   map<pair<pair<int,int>,const AhoCorasick<>*>, mint> memo;
96b8b260e1 2011-09-20        kinaba:   mint rec(int rest, const int C, const int found, const AhoCorasick<>* ac)
96b8b260e1 2011-09-20        kinaba:   {
96b8b260e1 2011-09-20        kinaba:     if( rest == 0 )
96b8b260e1 2011-09-20        kinaba:       return (bitcnt(found)==C ? 1 : 0);
96b8b260e1 2011-09-20        kinaba:     pair<pair<int,int>,const AhoCorasick*> key(make_pair(rest, found), ac);
96b8b260e1 2011-09-20        kinaba:     if( memo.count(key) )
96b8b260e1 2011-09-20        kinaba:       return memo[key];
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba:     mint sum = 0;
96b8b260e1 2011-09-20        kinaba:     for(char c='a'; c<='z'; ++c)
96b8b260e1 2011-09-20        kinaba:     {
96b8b260e1 2011-09-20        kinaba:       const AhoCorasick<>* t = ac->next(c);
96b8b260e1 2011-09-20        kinaba:       int f = found;
96b8b260e1 2011-09-20        kinaba:       for(set<int>::const_iterator it=t->accept().begin(); it!=t->accept().end(); ++it)
96b8b260e1 2011-09-20        kinaba:         f |= (1 << *it);
96b8b260e1 2011-09-20        kinaba:       sum += rec(rest-1, C, f, t);
96b8b260e1 2011-09-20        kinaba:     }
96b8b260e1 2011-09-20        kinaba:     return memo[key] = sum;
96b8b260e1 2011-09-20        kinaba:   }
96b8b260e1 2011-09-20        kinaba: };
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: 
96b8b260e1 2011-09-20        kinaba: // Powered by FileEdit
96b8b260e1 2011-09-20        kinaba: // Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom
96b8b260e1 2011-09-20        kinaba: // Powered by CodeProcessor
96b8b260e1 2011-09-20        kinaba: