HDU 2825 AC自動機+DP

題意：一個密碼，長度為 n，然後有m個magic words，這個密碼至少由k個magic words組成。 問這個密碼可能出現的總數。 思路：首先構造AC自動機，由於m很小，才10 ，我們可以使用二進制來表示每個magic words的使用情況。 對於dp[i][j][k]，表示長度為i 時，匹配到j這個節點，當前選取的magic words是k 狀態時的最大數量。

#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
using namespace std;  
#define MOD 20090717  
#define N 1111111  
int n , m , k ;  
int cnt ;  
struct AC_AUTO {  
    int next[26] ;  
    int fail ;  
    int st ;  
    void init() {  
        mem(next ,0) ;  
        fail = -1 ;  
        st = 0 ;  
    }  
} a[500000];  
int vis[111111] ;  
void show(int now) {  
    vis[now] = 1 ;  
    cout << now << " " << a[now].fail << endl;  
    for (int i = 0 ; i < 26 ; i ++ ) {  
        if(a[now].next[i] != 0 && !vis[a[now].next[i]]) {  
            show(a[now].next[i]) ;  
        }  
    }  
}  
void insert(char *s,int k) {  
    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].st |= (1 << k) ;  
}  
int q[111111] ;  
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] = 0 ;  
                else 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]].st |= a[a[p].next[i]].st ;  
                        break ;  
                    }  
                    p = a[p].fail ;  
                }  
                if(p == -1)a[a[front].next[i]].fail = 0 ;  
                q[tail ++] = a[front].next[i] ;  
            }  
        }  
    }  
}  
int dp[26][200][1 << 10] ;  
  
int solve() {  
    for (int i = 0 ; i <= n ; i ++ )  
        for (int j = 0 ; j <= cnt ; j ++ )  
            for (int x = 0 ; x <= 1 << m ; x ++ )  
                dp[i][j][x] = 0 ;  
    dp[0][0][0] = 1 ;  
    for (int i = 0 ; i < n ; i ++ )//長度為i時  
        for (int j = 0 ; j < cnt ; j ++ )//在第j個節點  
            for (int x = 0 ; x < 1 << m ; x ++) { //第x個狀態  
                if(!dp[i][j][x])continue ;  
                for (int y = 0 ; y < 26 ; y ++ ) { //字母y  
                    int newj = a[j].next[y] ;  
                    int newst = x | a[newj].st ;  
                    dp[i + 1][newj][newst] = (dp[i][j][x] + dp[i + 1][newj][newst] ) % MOD ;  
                }  
            }  
    int ans = 0 ;  
    for (int i = 0 ; i < 1 << m ; i ++ ) {  
        int ret = 0 ;  
        int d = i ;  
        for (; d ; d -= d & (-d) , ret ++) ;  
        if(ret < k )continue ;  
        for (int j = 0 ; j < cnt ; j ++ ) {  
            ans = (ans + dp[n][j][i]) % MOD ;  
        }  
    }  
    return ans ;  
}  
char in[111] ;  
int main() {  
    while(cin >> n >> m >> k, (n + m + k)) {  
        a[0].init() ;  
        cnt = 1 ;  
        for (int i = 0 ; i < m ; i ++ ) {  
            scanf("%s",in) ;  
            insert(in , i) ;  
        }  
        ac_bfs() ;  
        printf("%d\n",solve()) ;  
    }  
    return 0 ;  
}