POJ 2778 DNA Sequence ( Trie图、矩阵快速幂 )

题意 : 给出一些病毒串，问你由ATGC构成的长度为 n 且不包含这些病毒串的个数有多少个

分析：

我们先分析Tire 图的结构 ： Trie图是在AC自动机的原型上增添边使得状态可以快速转移，标记危险的节点（后缀是不良单词的节点）； 那我们是想构造长度是n不包含不良串对不对 ， 那是不是在trie图上从0节点走n步到安全节点的方案数（Trie图也是状态转移图）

在一个有向图中，A走k步到B的方案数（这显然是经典的矩阵快速幂问题），（原理需要自己搜索）先对原图建立一个邻接表M[i][j] , M[i][j] =1表示i到j有边直接相连,然后ans=pow(M,k)  ,ans[A][B] 为答案

#include<queue>

#include<stdio.h>

#include<string.h>

using namespace std;

const int Max_Tot = 1e2 + ;

const int Letter  = ;

const int MOD = 1e5;

int maxn;

int mp[];

struct mat{ int m[][]; }unit, M;

mat operator * (mat a, mat b)

{

    mat ret;

    long long x;

    for(int i=; i<maxn; i++){

        for(int j=; j<maxn; j++){

            x = ;

            for(int k=; k<maxn; k++){

                x += (long long)a.m[i][k]*b.m[k][j];

            }

            ret.m[i][j] = x % MOD;

        }

    }

    return ret;

}

inline void init_unit() { for(int i=; i<maxn; i++) unit.m[i][i] = ; }

mat pow_mat(mat a, int n)

{

    mat ret = unit;

    while(n){

        if(n&) ret = ret * a;

        a = a*a;

        n >>= ;

    }

    return ret;

}

struct Aho{

    struct StateTable{

        int Next[Letter];

        int fail, flag;

    }Node[Max_Tot];

    int Size;

    queue<int> que;

    inline void init(){

        while(!que.empty()) que.pop();

        memset(Node[].Next, , sizeof(Node[].Next));

        Node[].fail = Node[].flag = ;

        Size = ;

    }

    inline void insert(char *s){

        int now = ;

        for(int i=; s[i]; i++){

            int idx = mp[s[i]];

            if(!Node[now].Next[idx]){

                memset(Node[Size].Next, , sizeof(Node[Size].Next));

                Node[Size].fail = Node[Size].flag = ;

                Node[now].Next[idx] = Size++;

            }

            now = Node[now].Next[idx];

        }

        Node[now].flag = ;

    }

//1) 如果son[i]不存在，将它指向 当前结点now的fail指针指

//向结点的i号后继(保证一定已经计算出来)。

//2) 如果son[i]存在，将它的fail指针指向 当前结点now的fail

//指针指向结点的i号后继(保证一定已经计算出来)。

    inline void BuildFail(){

        Node[].fail = ;

        for(int i=; i<Letter; i++){

            if(Node[].Next[i]){

                Node[Node[].Next[i]].fail = ;

                que.push(Node[].Next[i]);

            }else Node[].Next[i] = ;///必定指向根节点

        }

        while(!que.empty()){

            int top = que.front(); que.pop();

            if(Node[Node[top].fail].flag) Node[top].flag = ;

            for(int i=; i<Letter; i++){

                int &v = Node[top].Next[i];

                if(v){

                    que.push(v);

                    Node[v].fail = Node[Node[top].fail].Next[i];

                }else v = Node[Node[top].fail].Next[i];

            }

        }

    }

    inline void BuildMatrix(){

        for(int i=; i<Size; i++)

            for(int j=; j<Size; j++)

                M.m[i][j] = ;

        for(int i=; i<Size; i++){

            for(int j=; j<Letter; j++){

                if(!Node[i].flag && !Node[ Node[i].Next[j] ].flag)

                    M.m[i][Node[i].Next[j]]++;

            }

        }

        maxn = Size;

    }

}ac;

char S[];

int main(void)

{

    mp['A']=,

    mp['T']=,

    mp['G']=,

    mp['C']=;

    int n, m;

    while(~scanf("%d %d", &m, &n)){

        ac.init();

        for(int i=; i<m; i++){

            scanf("%s", S);

            ac.insert(S);

        }

        ac.BuildFail();

        ac.BuildMatrix();

//        for(int i=0; i<10; i++){

//            for(int j=0; j<10; j++){

//                printf("%d ", M.m[i][j]);

//            }puts("");

//        }puts("");

        init_unit();

        M = pow_mat(M, n);

//        for(int i=0; i<10; i++){

//            for(int j=0; j<10; j++){

//                printf("%d ", M.m[i][j]);

//            }puts("");

//        }puts("");

        int ans = ;

        for(int i=; i<ac.Size; i++)

            ans += M.m[][i];

        ans %= MOD;

        printf("%d\n", ans);

    }

    return ;

}