AC自动机+状态压缩递推
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; using std::multimap; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PAIR; typedef multimap<int, int> MMAP; const int MAXN(110); const int SIGMA_SIZE(26); const int MAXM(110); const int MAXE(4000010); const int MAXH(18); const int INFI((INT_MAX-1) >> 2); const int BASE(131); const int MOD(20090717); const ULL LIM(1000000000000000ull); struct AC { int ch[MAXN][SIGMA_SIZE]; int val[MAXN]; int f[MAXN]; int size; void init() { memset(ch[0], 0, sizeof(ch[0])); f[0] = val[0] = 0; size = 1; } inline int idx(char temp) { return temp-'a'; } void insert(char *S, int tv) { int u = 0, id; for(; *S; ++S) { id = idx(*S); if(!ch[u][id]) { memset(ch[size], 0, sizeof(ch[size])); val[size] = 0; ch[u][id] = size++; } u = ch[u][id]; } val[u] |= (1 << tv); } int que[MAXN]; int front, back; void construct() { front = back = 0; int cur, u; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[0][i]; if(u) { que[back++] = u; f[u] = 0; } } while(front < back) { cur = que[front++]; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[cur][i]; if(u) { que[back++] = u; f[u] = ch[f[cur]][i]; val[u] |= val[f[u]]; } else ch[cur][i] = ch[f[cur]][i]; } } } }; AC ac; int table[26][110][1 << 10]; void solve(int len, int m, int K) { int lim = (1 << m); memset(table, 0, sizeof(table)); table[0][0][0] = 1; for(int i = 0; i < len; ++i) for(int j = 0; j < ac.size; ++j) for(int k = 0; k < lim; ++k) if(table[i][j][k]) { int tv = table[i][j][k]; for(int k2 = 0; k2 < SIGMA_SIZE; ++k2) { int ts = ac.ch[j][k2]; int &temp = table[i+1][ts][k|ac.val[ts]]; temp += tv; if(temp >= MOD) temp -= MOD; } } int ans = 0; for(int j = 0; j < lim; ++j) { int cnt = 0, tj = j; while(tj) { ++cnt; tj ^= tj&(-tj); } if(cnt < K) continue; for(int i = 0; i < ac.size; ++i) { ans += table[len][i][j]; if(ans >= MOD) ans -= MOD; } } printf("%d\n", ans); } char str[15]; int main() { int len, m, k; while(scanf("%d%d%d", &len, &m, &k), len+m+k) { ac.init(); for(int i = 0; i < m; ++i) { scanf("%s", str); ac.insert(str, i); } ac.construct(); solve(len, m, k); } return 0; }