TC SRM 519 600pt

自动机的DP

#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 305
#define ALP 26
#define MOD 1000000009
typedef long long ll;
using namespace std;
int n,m,k;
char s[52];
int next[MAXN][ALP],fail[MAXN],flag[MAXN],pos;
int newnode(){
    for(int i=0;i<ALP;i++)next[pos][i]=0;
    fail[pos]=flag[pos]=0;
    return pos++;
}
void insert(char *s,int id){
    int p=0;
    for(int i=0;s[i];i++){
        int k=s[i]-'a',&x=next[p][k];
        p=x?x:x=newnode();
    }
    flag[p]=1<<(id-1);
}
void makenext(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<ALP;i++){
            int v=next[u][i];
            if(v==0)next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(u&&v){
                fail[v]=next[fail[u]][i];
                //这里注意合并状态
                flag[v]|=flag[fail[v]];
            }
        }
    }
}
ll d[2][MAXN][64];
ll dp(){
    int full=(1<<m),cur=0;
    memset(d,0,sizeof(d));
    d[0][0][0]=1;
    for(int i=0;i<n;i++){
        cur^=1;
        for(int u=0;u<pos;u++){
            for(int s=0;s<full;s++)
                d[cur][u][s]=0;
        }
        for(int u=0;u<pos;u++){
            for(int s=0;s<full;s++){
                //如果这个状态还没有到达过
                int bit=0;
                for(int i=s;i;bit++,i-=(i&-i));
                if(bit>k)continue;
                if(d[cur^1][u][s]==0)continue;
                //用这个状态跟新它的后继节点
                for(int k=0;k<ALP;k++){
                    int v=next[u][k];
                    ll &x=d[cur][v][flag[v]|s];
                    x=(x+d[cur^1][u][s])%MOD;
                }
            }
        }
    }
    //统计第n步走过=k个单词的状态的总数
    ll ans=0;
    for(int s=0;s<full;s++){
        int bit=0;
        for(int i=s;i;bit++,i-=(i&-i));
        if(bit!=k)continue;
        for(int i=0;i<pos;i++)
            ans=(ans+d[cur][i][s])%MOD;
    }
    return ans;
}
int main(){
    while(scanf("%d%d%d",&n,&m,&k)){
        pos=0;newnode();
        for(int i=1;i<=m;i++){
            scanf("%s",s);
            insert(s,i);
        }
        makenext();
        ll ans=dp();
        printf("%lld\n",ans);
    }
    return 0;
}