[POJ 2778][AC 自動機] DNA Sequence

原題連結

將所有給出來的字串建造出AC自動機，那麼每生成一新字元相當於在AC自動機上走一步，題意即走n步而不碰到任何單字節點的走法。

首先需要把AC自動機所有不存在的邊補上，這可以在建造fail函數時一起進行。
這樣我們就得到了一個真正的「自動機」，接著構造轉移矩陣，構造時不要理會那些單字節點，最後透過快速冪解決問題。

時間複雜度比較有趣，因為單字量很少，trie上最多100個節點，複雜度瓶頸在於矩陣快速冪，是O(sz^3 * log(n))，注意如果直接將maxnode做為運算基準會TLE，要將Trie上的size拿來減少運算量

#define LL long long
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const LL maxlen=10+5;
const LL SIGMA_SIZE=4;
const LL maxnode=100+5;
const LL mod=100000;
LL sz;
struct Matrix
{
    LL mat[maxnode][maxnode];
    Matrix operator * (const Matrix& rhs) const
    {
        Matrix ret;
        for(LL i=0;i<=sz;i++)
            for(LL j=0;j<=sz;j++)
            {
                ret.mat[i][j]=0;
                for(LL k=0;k<=sz;k++) (ret.mat[i][j]+=mat[i][k]*rhs.mat[k][j])%=mod;
            }
        return ret;
    }
};
struct AhoCorasick
{
    Matrix Mat;
    LL node[maxnode][SIGMA_SIZE];
    LL fail[maxnode],match[maxnode];
    inline void init() {sz=0;}
    inline LL idx(char c)
    {
        if(c=='A') return 0;
        if(c=='T') return 1;
        if(c=='C') return 2;
        else return 3;
    }
    void insert(char* S)
    {
        LL n=strlen(S),now=0;
        for(LL i=0;i<n;i++)
        {
            LL c=idx(S[i]);
            if(!node[now][c]) node[now][c]=++sz;
            now=node[now][c];
        }
        match[now]=1;
    }
    void getfail()
    {
        queue<int> Q;
        for(LL i=0;i<SIGMA_SIZE;i++) if(node[0][i]) Q.push(node[0][i]);
        while(!Q.empty())
        {
            LL now=Q.front();Q.pop();
            for(LL i=0;i<SIGMA_SIZE;i++)
            {
                if(!node[now][i]) {node[now][i]=node[fail[now]][i];continue;}
                LL j=fail[now],nx=node[now][i];
                while(j && !node[j][i]) j=fail[j];
                fail[nx]=node[j][i];
                match[nx]|=match[fail[nx]];
                Q.push(nx);
            }
        }
    }
    bool vis[maxnode];
    void dfs(LL now)
    {
        vis[now]=1;
        for(LL i=0;i<SIGMA_SIZE;i++)
        {
            LL to=node[now][i];
            if(match[to]) continue;
            Mat.mat[now][to]++;
            if(!vis[to]) dfs(to);
        }
    }
    void solve(LL n)
    {
        dfs(0);
        
        Matrix ans;
        for(LL i=0;i<=sz;i++) ans.mat[i][i]=1;
        for(;n;n>>=1,Mat=Mat*Mat)
        {
            if(n&1) ans=ans*Mat;
        }
        LL tot=0;
        for(LL i=0;i<=sz;i++) if(!match[i]) (tot+=ans.mat[0][i])%=mod;
        printf("%lld\n",tot);
    }
}AC;
char s[maxlen];
int main()
{
    LL m,n;
    scanf("%lld%lld",&m,&n);
    for(LL i=0;i<m;i++)
    {
        scanf("%s",s);
        AC.insert(s);
    }
    AC.getfail();
    AC.solve(n);
}