hdu2825 - (AC 로봇 + 전압 DP)

#include
#include
#include
#include
#include
#include
using namespace std;
const int mod = 20090717;
int n,m,k;
struct tried{
    int dp[30][105][1<<10];
    int ch[105][26];
    int f[105];
    int v[105];
    int sz;
    void init(){
        memset(f,0,sizeof(f));
        memset(ch[0],0,sizeof(ch[0]));
        memset(v,0,sizeof(v));
        memset(dp,0,sizeof(dp));
        dp[0][0][0] = 1;
        sz = 1;
    }
    int idx(char c){
        return c-'a';
    }
    int num(int x){
        int ans = 0;
        while(x){
            if(x&1) ans++;
            x /= 2;
        }
        return ans;
    }
    void insert(char *s,int id){
        int u = 0,len = strlen(s);
        for(int i = 0; i < len; i++){
            int d = idx(s[i]);
            if(!ch[u][d]){
                memset(ch[sz],0,sizeof(ch[sz]));
                ch[u][d] = sz++;
            }
            u = ch[u][d];
        }
        v[u] = 1<q;
        for(int d = 0; d < 26; d++)
            if(ch[u][d])
                q.push(ch[u][d]);
        while(!q.empty()){
            u = q.front();
            q.pop();
            v[u] |= v[f[u]];
            for(int d = 0; d < 26; d++){
                if(!ch[u][d]){
                    ch[u][d] = ch[f[u]][d];
                    continue;
                }
                int ret = ch[u][d];
                f[ret] = ch[f[u]][d];
                q.push(ret);
            }
        }
    }
    void work(){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < sz; j++)
                for(int k = 0; k < (1<=k)
                    ans = (ans+dp[n][i][j])%mod;
        printf("%d
",ans);
    }
}word;
char s[105];
int main(){
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        if(n==0&&m==0&&k==0)
            break;
        word.init();
        for(int i = 0; i < m; i++){
            scanf("%s",s);
            word.insert(s,i);
        }
        word.getfail();
        word.work();
    }
    return 0;
}