poj 2778 AC自动机+矩阵快速幂

时间：2023-03-08 21:00:32

题目链接：https://vjudge.net/problem/POJ-2778

题意：输入n和m表示n个病毒，和一个长为m的字符串，里面只可以有'A'，'C'，'G'，'T' 这四个字符，现在问这个长为m的字符串里面不可以出现任何病毒的情况有多少。

参考的两篇博客：

http://www.cnblogs.com/LQLlulu/p/9344774.html

https://blog.****.net/morgan_xww/article/details/7834801

上面的博客写得很好，可以主要看上面的博客（两个一起看）。

写点东西，不一定对。

因为最多10个病毒，每个病毒最多10个字符，所以我们trie树上最多有100个点，其他空的点都指向根节点（也就是说我们把所有的空的节点看成0），这样我们可以到达的点就只有100个（再重复一遍：我们把trie树上面的空节点一律指向根节点，看成0），同时因为有些点是单词的结尾或者他的fail[u]是单词结尾（fail[u]是单词结尾说明当前位置的后缀和fail[u]上的单词相同，这个后缀也不能到达）。

我们一开始先构建一个cnt*cnt的邻接矩阵mat（cnt是trie树上面的节点个数），刚刚构建的mat[i][j]代表从编号为i的点走一步到达编号为j的点的合法（就是不经过单词结尾或fail[u]是单词结尾的点），在离散数学里面有一个结论，就是已知cnt个点之间两两互达（走一步）的可能数量（就是这个cnt*cnt的矩阵已经有了），那么如果我们要计算他们两两之间走n步到达的可能数量，只需要求出矩阵的n次方，这个矩阵的n次方就是点与点之间走n步到达的可能数量，这个可以联想矩阵乘法的计算过程。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 105
],fail[maxn],val[maxn];
LL mat[maxn][maxn],f[maxn][maxn],ss[maxn][maxn];
//mat[i][j]记录从i到j有多少种可能，f[0][i]记录以i结束的合法可能，其它维没用，ss用来计算时暂时存储
int n,m,k,t,cnt;
];
void init(){
    memset(trie,,sizeof(trie));
    memset(fail,,sizeof(fail));
    memset(val,,sizeof(val));
    memset(mat,,sizeof(mat));
    memset(f,,sizeof(f));
    f[][]=;        //一开始把根节点赋值为1,因为我们只需要第一行，所以可以只把f[0][0]赋值为1
    /*for(int i=0;i<maxn;i++)
    f[i][i]=1; */    //也可以这样
    cnt=;
}
int getID(char a){
    if(a=='A')
    ;
    if(a=='T')
    ;
    if(a=='C')
    ;
    if(a=='G')
    ;
}
void insert(char *s){
    ;
    ;s[i];i++){
        int id=getID(s[i]);
        )
        trie[root][id]=++cnt;
        root=trie[root][id];
    }
    val[root]=;//标记单词结尾
}
void build_fail(){
    queue<int>q;
    ;
    ;i<;i++){
        if(trie[root][i])
        q.push(trie[root][i]);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(val[fail[u]])//如果这个后缀是一个病毒，那么这个后缀也不可以到达
        val[u]=;
        ;i<;i++){
            if(trie[u][i]){
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }else{
                trie[u][i]=trie[fail[u]][i];
            }
        }
    }
}
void build_mat(){//建图
    ;i<=cnt;i++){
        ;j<;j++){
            &&val[i]==)//当前状态或接下来的的状态是病毒都是不可以到达的
            mat[i][trie[i][j]]++;
        }
    }
}
void muti(LL a[][maxn],LL b[][maxn]){//矩阵快速幂
    memset(ss,,sizeof(ss));
    ;k<=cnt;k++)
    ;i<=cnt;i++){
        ;j<=cnt;j++){
            ss[i][j]+=a[i][k]*b[k][j];
            ss[i][j]%=;
        }
    }
    ;i<=cnt;i++){
        ;j<=cnt;j++){
            a[i][j]=ss[i][j];
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        ;i<n;i++){
            scanf("%s",s);
            insert(s);
        }
        build_fail();
        build_mat();//获得走1步时的矩阵
        while(m){
            )
            muti(f,mat);
            muti(mat,mat);
            m>>=;
        }
        LL ans=;
        ;i<=cnt;i++)
        ans=(ans+f[][i])%;
        printf("%lld\n",ans);
    }
    ;
}

相关文章