HDU 2825 Wireless Password(AC自动机+DP)

做题，
  1 #include <cstdio>
  2 #include <string>
  3 #include <cstring>
  4 using namespace std;
  5 #define MOD 20090717
  6 int trie[351][26];
  7 int o[351];
  8 int fail[351];
  9 int que[351];
 10 int dp[2][351][1024];
 11 int flag[1024];
 12 int t;
 13 void CL()
 14 {
 15     memset(trie,-1,sizeof(trie));
 16     memset(dp,0,sizeof(dp));
 17     memset(o,0,sizeof(o));
 18     t = 1;
 19 }
 20 void insert(char *s,int num)
 21 {
 22     int root,i,len;
 23     len = strlen(s);
 24     root = 0;
 25     for(i = 0;i < len;i ++)
 26     {
 27         if(trie[root][s[i]-'a'] == -1)
 28         trie[root][s[i]-'a'] = t ++;
 29         root = trie[root][s[i]-'a'];
 30     }
 31     o[root] |= 1<<num;
 32 }
 33 void build_ac()
 34 {
 35     int head,tail,front,i;
 36     head = tail = 0;
 37     for(i = 0;i < 26;i ++)
 38     {
 39         if(trie[0][i] != -1)
 40         {
 41             fail[trie[0][i]] = 0;
 42             que[tail++] = trie[0][i];
 43         }
 44         else
 45         {
 46             trie[0][i] = 0;
 47         }
 48     }
 49     while(head != tail)
 50     {
 51         front = que[head++];
 52         o[front] |= o[fail[front]];
 53         for(i = 0;i < 26;i ++)
 54         {
 55             if(trie[front][i] != -1)
 56             {
 57                 que[tail++] = trie[front][i];
 58                 fail[trie[front][i]] = trie[fail[front]][i];
 59             }
 60             else
 61             {
 62                 trie[front][i] = trie[fail[front]][i];
 63             }
 64         }
 65     }
 66 }
 67 int main()
 68 {
 69     int n,m,r,k,i,j,u,x,y;
 70     char str[101];
 71     for(i = 0;i < 1024;i ++)
 72     {
 73         for(j = 0;j < 10;j ++)
 74         {
 75             if(i&(1<<j)) flag[i] ++;
 76         }
 77     }
 78     while(scanf("%d%d%d",&n,&m,&r)!=EOF)
 79     {
 80         if(n == 0&&m == 0&&r == 0) break;
 81         CL();
 82         for(i = 0;i < m;i ++)
 83         {
 84             scanf("%s",str);
 85             insert(str,i);
 86         }
 87         build_ac();
 88         dp[0][0][0] = 1;
 89         x = 0;y = 1;
 90         for(i = 0;i < n;i ++)
 91         {
 92             memset(dp[y],0,sizeof(dp[y]));
 93             for(j = 0;j < t;j ++)
 94             {
 95                 for(k = 0;k < (1<<m);k ++)
 96                 {
 97                     if(dp[x][j][k] == 0) continue;
 98                     for(u = 0;u < 26;u ++)
 99                     {
100                         int temp =  trie[j][u];
101                         dp[y][temp][k|o[temp]] += dp[x][j][k];
102                         if(dp[y][temp][k|o[temp]] >= MOD)
103                         dp[y][temp][k|o[temp]] -= MOD;
104                     }
105                 }
106             }
107             swap(x,y);
108         }
109         int ans = 0;
110         for(i = 0;i < t;i ++)
111         {
112             for(j = 0;j < (1<<m);j ++)
113             {
114                 if(flag[j] >= r)
115                 ans = (ans + dp[x][i][j])%MOD;
116             }
117         }
118         printf("%d
",ans);
119     }
120     return 0;
121 }
找找手感。