HDU 2825 Wireless Password

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 105;
 4 const int mod = 20090717;
 5 int dp[2][maxn][1<<10];
 6 struct Trie {
 7     int ch[maxn][26],fail[maxn],cnt[maxn],tot;
 8     int newnode() {
 9         memset(ch[tot],0,sizeof ch[tot]);
10         fail[tot] = cnt[tot] = 0;
11         return tot++;
12     }
13     void init() {
14         tot = 0;
15         newnode();
16     }
17     void insert(char *str,int pos,int rt = 0) {
18         for(int i = 0; str[i]; ++i) {
19             int &x = ch[rt][str[i]-‘a‘];
20             if(!x) x = newnode();
21             rt = x;
22         }
23         cnt[rt] |= (1<<pos);
24     }
25     void build(int rt = 0) {
26         queue<int>q;
27         for(int i = 0; i < 26; ++i)
28             if(ch[rt][i]) q.push(ch[rt][i]);
29         while(!q.empty()) {
30             rt = q.front();
31             q.pop();
32             cnt[rt] |= cnt[fail[rt]];
33             for(int i = 0; i < 26; ++i) {
34                 int &x = ch[rt][i],y = ch[fail[rt]][i];
35                 if(x) {
36                     q.push(x);
37                     fail[x] = y;
38                 } else x = y;
39             }
40         }
41     }
42     void solve(int n,int m,int z) {
43         memset(dp,0,sizeof dp);
44         dp[0][0][0] = 1;
45         int cur = 0;
46         for(int i = 1; i <= n; ++i) {
47             for(int j = 0; j < tot; ++j) {
48                 for(int k = 0; k < (1<<m); ++k) {
49                     if(!dp[cur][j][k] || (k&cnt[j] != cnt[j])) continue;
50                     for(int t = 0; t < 26; ++t) {
51                         int x = ch[j][t];
52                         dp[cur^1][x][k|cnt[x]] += dp[cur][j][k];
53                         dp[cur^1][x][k|cnt[x]] %= mod;
54                     }
55                 }
56             }
57             memset(dp[cur],0,sizeof dp[cur]);
58             cur ^= 1;
59         }
60         int ret = 0;
61         for(int i = 0; i < tot; ++i)
62             for(int j = 0; j < (1<<m); ++j) {
63                 int nd = 0;
64                 for(int k = j; k; k >>= 1) if(k&1) ++nd;
65                 if(nd >= z) ret = (ret + dp[cur][i][j])%mod;
66             }
67         cout<<ret<<endl;
68     }
69 }ac;
70 int main() {
71     int n,m,k;
72     char str[maxn];
73     while(scanf("%d%d%d",&n,&m,&k),n||m||k){
74         ac.init();
75         for(int i = 0; i < m; ++i){
76             scanf("%s",str);
77             ac.insert(str,i);
78         }
79         ac.build();
80         ac.solve(n,m,k);
81     }
82     return 0;
83 }