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

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <climits>//形如INT_MAX一类的  
#define MAX 100005  
#define mod 20090717  
#define INF 0x7FFFFFFF  
#define REP(i,s,t) for(int i=(s);i<=(t);++i)  
#define LL long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define L(x) x << 1  
#define R(x) x << 1 | 1  
# define eps 1e-5  
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂  
using namespace std;  
  
struct Trie {  
    int next[26] ;  
    int fail ;  
    int buff ;  
    void init() {  
        memset(next,0,sizeof(next)) ;  
        fail = -1 ;  
        buff = 0 ;  
    }  
} a[111];  
int cnt,n,m,K;  
int q[111] , dp[30][111][1 << 10];  
char keyword[22];  
  
void insert(char *s,int pos) {  
    int p = 0 ;  
    for(int i = 0 ; s[i] ; i ++) {  
        int t = s[i] - 'a' ;  
        if(a[p].next[t] == 0) {  
            a[cnt].init();  
            a[p].next[t] = cnt ++;  
        }  
        p = a[p].next[t] ;  
    }  
    a[p].buff = 1 << pos;  
}  
void ac_bfs() {  
    int i,head = 0,tail = 0;  
    q[tail ++] = 0;  
    while(head < tail) {  
        int front = q[head ++];  
        for(i = 0; i < 26 ; i ++) {  
            if(a[front].next[i] == 0) {  
                if(front != 0) a[front].next[i] = a[a[front].fail].next[i];  
            } else {  
                int p = a[front].fail ;  
                while(p != -1) {  
                    if(a[p].next[i] != 0) {  
                        a[a[front].next[i]].fail = a[p].next[i] ;  
                        a[a[front].next[i]].buff |= a[a[p].next[i]].buff;//状态合并，因为如果fail指向的节点也是某个magic word的结尾，那么相当于一次找到两个magic word  
                        break ;  
                    }  
                    p = a[p].fail ;  
                }  
                if(p == -1) a[a[front].next[i]].fail = 0 ;  
                q[tail ++] = a[front].next[i] ;  
            }  
        }  
    }  
}  
  
int calone(int x) {  
    int cal = 0;  
    while(x) {  
        if(x & 1) cal ++;  
        x = x >> 1;  
    }  
    return cal;  
}  
  
void solve() {  
    dp[0][0][0] = 1;  
    int total = 1 << m;  
    for(int i=0; i<n; i++) {  
        for(int j=0; j<cnt; j++) {  
            for(int k=0; k<total; k++) {  
                if(dp[i][j][k] == 0) continue;  
                for(int l=0; l<26; l++) {  
                    int buff = a[a[j].next[l]].buff;  
                    dp[i+1][a[j].next[l]][k | buff] = (dp[i+1][a[j].next[l]][k | buff] + dp[i][j][k]) % mod;  
                }  
            }  
        }  
    }  
    int ans = 0;  
    for(int j=0; j<cnt; j++) {  
        for(int k=0; k<total; k++) {  
            if(calone(k) < K) continue;  
            ans = (ans + dp[n][j][k] ) % mod;  
        }  
    }  
    printf("%d\n",ans);  
}  
  
int main() {  
    while(scanf("%d%d%d",&n,&m,&K)) {  
        if(n == 0 && m == 0 && K == 0) break;  
        a[0].init();  
        cnt = 1;  
        for(int i=0; i<m; i++) {  
            scanf("%s",keyword);  
            insert(keyword,i);  
        }  
        ac_bfs();  
        for(int i=0; i<=n; i++) {  
            for(int j=0; j<cnt; j++) {  
                for(int l=0; l<(1<<m); l++) {  
                    dp[i][j][l] = 0;  
                }  
            }  
        }  
        solve();  
    }  
    return 0;  
}