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