POJ2778：

• 传送门:POJ2778

• 类似题目：BZOJ1009

  
  

　　很容易想到，本题是一道AC自动机上的DP。
　　定义状态函数$f(i,j)$，代表目标串的第i位匹配到了AC自动机中的节点j的方案数。
　　那么显然，答案等于$\sum_{val[j]=0,last[j]=0} f(n,j)$。
　　考虑状态函数的转移，引入辅助函数$P(i,j)$，代表从AC自动机的第i个节点转移到第j个节点的方案数，其中若i或j为危险节点，则$P(i,j)=0$。
　　容易发现，$f(i,j)=\sum f(i-1,k) \times P(k,j)$。
　　这式子可以看作两个矩阵间的乘法，而$P(i,j)$可以简单地预处理出来。
　　边界条件是，$f(1,i)=1$，其中i=ch[0][1]。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
typedef long long ll;
using namespace std;
const int maxnode=15*15,sigma=4;
const int MOD=100000;
queue<int> Q;
struct Trie{
    int tot;
    int ch[maxnode][sigma];
    int f[maxnode];
    bool danger[maxnode]; 
    Trie(){
        tot=1;
        memset(ch,0,sizeof(ch));
        memset(f,0,sizeof(f));
        memset(danger,false,sizeof(danger));
    }
    inline int idx(char a){
        if(a=='A')
            return 0;
        if(a=='C')
            return 1;
        if(a=='G')
            return 2;
        return 3;
    }
    void Clear(){
        tot=1;
        memset(ch[0],0,sizeof(ch[0]));
        memset(danger,false,sizeof(danger));
    }
    int newnode(){
        memset(ch[tot],0,sizeof(ch[tot]));
        return tot++;
    }
    void Insert(string s){
        int len=s.length();
        int u=0;
        for(int i=0;i<len;i++){
            if(ch[u][idx(s[i])]==0)             
                ch[u][idx(s[i])]=newnode();
            u=ch[u][idx(s[i])];
        }
        danger[u]=true;
    }
    void Build(){
        while(!Q.empty())
            Q.pop();
        for(int i=0;i<sigma;i++){
            if(ch[0][i]){
                f[ch[0][i]]=0;
                Q.push(ch[0][i]);
            }
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<sigma;i++){
                if(ch[u][i]==0){
                    ch[u][i]=ch[f[u]][i];
                    continue;
                }
                int v=ch[u][i];
                Q.push(v);
                int r=f[u];
                while(r&&ch[r][i]==0)
                    r=f[r];
                f[v]=ch[r][i];
                danger[v]|=danger[f[v]];
            }
        }
    }
};
struct Matrix{
    int l,r;
    ll a[maxnode][maxnode];
    Matrix(){
        l=r=0;
        memset(a,0,sizeof(a));
    }
    Matrix operator *(const Matrix& o)const{
        Matrix c;
        for(int i=0;i<=l;i++)
            for(int j=0;j<=o.r;j++)
                for(int k=0;k<=r;k++){
                    c.a[i][j]+=(a[i][k]*o.a[k][j]);
                    c.a[i][j]%=MOD;
                }
        c.l=l;
        c.r=o.r;
        return c;
    }
    void Print(){
        for(int i=0;i<=l;i++){
            for(int j=0;j<=r;j++)
                cout<<a[i][j]<<" ";
            printf("\n");
        }
    }
};
Trie Aho_Corasick;
Matrix Base;
Matrix E;
Matrix From;
int n;
int m;
string S;
void First()
{
    Aho_Corasick.Build();
    Base.l=Base.r=Aho_Corasick.tot-1;
    E.l=E.r=Base.l;
    From.l=0;
    From.r=Base.r;
    for(int i=0;i<=E.l;i++)
        E.a[i][i]=1;
    for(int i=0;i<=Base.l;i++)
        if(!Aho_Corasick.danger[i])
            for(int j=0;j<=Base.r;j++)
                if(!Aho_Corasick.danger[j])
                    for(int k=0;k<sigma;k++)
                        if(Aho_Corasick.ch[i][k]==j)
                            Base.a[i][j]++;
    for(int j=0;j<sigma;j++)
        From.a[0][Aho_Corasick.ch[0][j]]++;
}
Matrix Power(Matrix O,int a)
{
    Matrix ans=E;
    while(a>0){
        if(a&1)
            ans=ans*O;
        O=O*O;
        a>>=1;
    }
    return ans;
}
void Solve()
{
    From=From*Power(Base,n-1);
    ll ans=0;
    for(int i=0;i<=From.r;i++)
        if(!Aho_Corasick.danger[i])
            ans+=From.a[0][i];
    cout<<ans%MOD;
}
void ReadData()
{
    freopen("POJ2778.in","r",stdin);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        cin>>S;
        Aho_Corasick.Insert(S);
    }
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    ReadData();
    First();
    Solve();
    Close();
    return 0;
}