DNA Sequence

DNA Sequence

题意：题目给m个病毒串，问不包含病毒串的长度为n的DNA p段有几个

难度：两颗星

思路：

这个图是例子{“ACG”,”C”},构建树后如图所示，从每个结点出发都有4条边（A,T,C,G）
•从状态0出发走一步有4种走法：
–走A到状态1（安全）；
–走C到状态4（危险）；
–走T到状态0（安全）；
–走G到状态0（安全）；
•所以当n=1时，答案就是3
•当n=2时，就是从状态0出发走2步，就形成一个长度为2的字符串，只要路径上没有经过危险结点，有几种走法，那么答案就是几种。依此类推走n步就形成长度为n的字符串。
matrix矩阵如下(矩阵i行j列的权值是结点i转移到结点j的方案数)：
n=1
2 1 0 0 0
2 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
n=2
6 3 0 0 0
6 3 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

代码+注释：

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<queue>
#define ll long long
using namespace std;
int ch[111][4],f[111],sz;
int idx[128];            //病毒只有4个字符，可以简单处理 
bool val[111];
/*题目的数据范围是10个长度10的病毒串，所以Trie树中最多101左右个节点，
那么AC自动机整个转移就可以构建一张101*101的邻接矩阵，矩阵i行j列的权值是节点i转移到节点j的方案数。
而进行k次转移，从节点i转移到节点j的方案数是这个矩阵的k次幂，这个结论离散数学的图论有（我没学，只能信了）*/
struct Trie{
    Trie(){ sz = 0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);};
    void insert(char *s){
        int u=0;
        for(int i=0;s[i];++i){
            int c=idx[s[i]];
            if(!ch[u][c]) ch[u][c] = ++sz;
            u=ch[u][c];
        }
        val[u]=1;    //val数组标记节点是否为单词结尾，last数组和val数组是同一个数组，没必要都要，所以这里没有last数组 
    }
};
//fail指针没必要初始化，从前往后计算会覆盖上一次的结果 
int getFail(){
    queue<int>q; int u;
    f[0] = 0;
    for(int c=0;c<4;++c){
        u = ch[0][c];
        if(u)  { f[u]=0; q.push(u);}
    }
    while(!q.empty()){
        int r=q.front(); q.pop();
        for(int c=0;c<4;++c){
            u=ch[r][c];
            if(!u){
                ch[r][c]=ch[f[r]][c];    //移花接木，因为是从前往后计算的，如果当前位置没有节点，
        //而前面有这条边，则将最近的一个边的出节点复制过来，方便后续寻找fail指针的简化，只要找一次就能得到fail指针
        //因为是将前面的节点移过来，所以不必再对这个节点继续操作了 
                continue;
            }
            q.push(u);
            f[u] = ch[f[r]][c];            //可以直接这样得益于上面移花接木的操作 
            val[u]|=val[ch[f[r]][c]];    //如果该节点的fail指针是单词结尾，这个节点也不能取 
        /*只要算出后缀含有病毒的点即可，因为矩阵是通过相互到达传递的，
        其后的点只有这个危险点能到达，危险点的行和列全是0，则其后的点也不会参与运算。
        可以这样说，0行里危险点的列和其后的列从来都是0，因为不能到达。*/ 
        }
    }
}
struct mat {
    ll matrix[111][111];
    mat() {
        memset(matrix,0,sizeof(matrix));
    }
};
mat operator*(const mat &m1,const mat &m2){
    mat m;
    for(int i=0; i<=sz; ++i){
        for(int j=0; j<=sz; ++j){
            for(int k=0; k<=sz; ++k){
                m.matrix[i][j]+=m1.matrix[i][k]*m2.matrix[k][j];
                m.matrix[i][j]%=100000;
            }
        }
    }
    return m;
}
char str[11];
int m,n;
int main(){
    idx['A']=0; idx['C']=1; idx['T']=2; idx['G']=3;
    while(~scanf("%d%d",&m,&n)) {
        Trie trie;
        while(m--){
            scanf("%s",str);
            trie.insert(str);
        }
        getFail();
        mat res,a;
        for(int i=0;i<=sz;++i)    res.matrix[i][i]=1;
        for(int i=0;i<=sz;++i) {
            if(val[i])    continue;
            for(int j=0;j<4;++j) {
                if(val[ch[i][j]])    continue;
                ++a.matrix[i][ch[i][j]];
            }
        }
        for(int i=0;i<=sz;++i) {//打印矩阵
            for(int j=0;j<=sz;++j) {
                printf("%d ",a.matrix[i][j]);
            }
            puts("");
        } 
        while(n) {
            if(n&1)    res=res*a;
            a=a*a;
            n>>=1;
        }
        for(int i=0;i<=sz;++i) {//打印矩阵
            for(int j=0;j<=sz;++j) {
                printf("%d ",res.matrix[i][j]);
            }
            puts("");
        } 
        ll ans=0;
        for(int i=0;i<=sz;++i)
            ans=(ans+res.matrix[0][i])%100000;
//所有串都是从根节点开始的 
        printf("%lld\n",ans);
    }
}

无注释代码：

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<queue>
#define ll long long
using namespace std;
int ch[111][4],f[111],sz;
int idx[128];
bool val[111];
struct Trie{
    Trie(){ sz = 0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);};
    void insert(char *s){
        int u=0;
        for(int i=0;s[i];++i){
            int c=idx[s[i]];
            if(!ch[u][c]) ch[u][c] = ++sz;
            u=ch[u][c];
        }
        val[u]=1;
    }
};
int getFail(){
    queue<int>q; int u;
    f[0] = 0;
    for(int c=0;c<4;++c){
        u = ch[0][c];
        if(u)  { f[u]=0; q.push(u);}
    }
    while(!q.empty()){
        int r=q.front(); q.pop();
        for(int c=0;c<4;++c){
            u=ch[r][c];
            if(!u){
                ch[r][c]=ch[f[r]][c];
                continue;
            }
            q.push(u);
            f[u] = ch[f[r]][c];
            val[u]|=val[ch[f[r]][c]];
        }
    }
}
struct mat {
    ll matrix[111][111];
    mat() {
        memset(matrix,0,sizeof(matrix));
    }
};
mat operator*(const mat &m1,const mat &m2){
    mat m;
    for(int i=0; i<=sz; ++i){
        for(int j=0; j<=sz; ++j){
            for(int k=0; k<=sz; ++k){
                m.matrix[i][j]+=m1.matrix[i][k]*m2.matrix[k][j];
                m.matrix[i][j]%=100000;
            }
        }
    }
    return m;
}
char str[11];
int m,n;
int main(){
    idx['A']=0; idx['C']=1; idx['T']=2; idx['G']=3;
    while(~scanf("%d%d",&m,&n)) {
        Trie trie;
        while(m--){
            scanf("%s",str);
            trie.insert(str);
        }
        getFail();
        mat res,a;
        for(int i=0;i<=sz;++i)    res.matrix[i][i]=1;
        for(int i=0;i<=sz;++i) {
            if(val[i])    continue;
            for(int j=0;j<4;++j) {
                if(val[ch[i][j]]) continue;
                ++a.matrix[i][ch[i][j]];
            }
        }
        while(n) {
            if(n&1)    res=res*a;
            a=a*a;
            n>>=1;
        }
        ll ans=0;
        for(int i=0;i<=sz;++i)
            ans=(ans+res.matrix[0][i])%100000;
        printf("%lld\n",ans);
    }
}