AC自动机+矩阵乘法

DNA Sequence
题意：
有m种DNA序列是有疾病的，问有多少种长度为n的DNA序列不包含任何一种有疾病的DNA序列。（仅含A,T,C,G四个字符）
题解1: 　　题解2:　　题解3:　　　参考1

以下内容参考自这里
样例m=4,n=3,{“AA”,”AT”,”AC”,”AG”}
答案为36，表示有36种长度为3的序列可以不包含疾病
这个和矩阵有什么关系呢？？？


•上图是例子{“ACG”,”C”},构建trie图后如图所示，从每个结点出发都有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的字符串。
•建立trie图的邻接矩阵M：
2 1 0 0 1
2 1 1 0 0
1 1 0 1 1
2 1 0 0 1
2 1 0 0 1
M[i,j]表示从结点i到j只走一步有几种走法。
那么M的n次幂就表示从结点i到j走n步有几种走法。

题解:
就是通过AC自动机得到合法的转移,然后对应的方法数+1

这是通过构建trie图的代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int MAXN=110;
const long long MOD=100000l;
struct Node
{
    bool virus;
    int fail;
    int next[4];
};
Node trie[MAXN];
int trie_s;
int key(char c)
{
    int index=4;
    switch(c)
    {
        case 'A':index--;
        case 'C':index--;
        case 'G':index--;
        case 'T':index--;
    }
    return index;
}
long long A[MAXN][MAXN],R[MAXN][MAXN];
void insert(char *str)
{
    int len=strlen(str);
    int p=1;
    for(int i=0;i<len;i++)
    {
        int pos=key(str[i]);
        if(!trie[p].next[pos])
        {
            trie[p].next[pos]=++trie_s;
        }
        p=trie[p].next[pos];
    }
    trie[p].virus=true;
}
void getFail()
{
    queue<int> que;
    que.push(1);
    int curr,son,temp;
    while(!que.empty())
    {
        curr=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            son=trie[curr].next[i];
            if(son==0)
            {
                if(curr==1) trie[curr].next[i]=1;
                else trie[curr].next[i]=trie[trie[curr].fail].next[i];
            }
            else
            {
                if(curr==1) trie[son].fail=1;
                else
                {
                    temp=trie[curr].fail;
                    while(temp!=0)
                    {
                        if(trie[temp].next[i])
                        {
                            trie[son].fail=trie[temp].next[i];
                            break;
                        }
                        temp=trie[temp].fail;
                    }
                    if(temp==0) trie[son].fail=1;
                    if(temp!=0&&trie[trie[son].fail].virus) trie[son].virus=true;
                }
                que.push(son);
            }
        }
    }
}
void getPreMatrix()
{
    int son;
    memset(A,0,sizeof(A));
    for(int i=1;i<=trie_s;i++)
    {
        if(trie[i].virus) continue;
        for(int j=0;j<4;j++)
        {
            son=trie[i].next[j];
            if(trie[son].virus) continue;
            A[i][son]++;
        }
    }
}
void matrixMulti(long long a[MAXN][MAXN],long long b[MAXN][MAXN])
{
    long long c[MAXN][MAXN];
    memset(c,0,sizeof(c));
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            for(int k=1;k<=trie_s;k++)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            a[i][j]=c[i][j];
        }
    }
}
void getResMatrix(int n)
{
    memset(R,0,sizeof(R));
    for(int i=1;i<=trie_s;i++)
    {
        R[i][i]=1;
    }
    while(n)
    {
        if(n&1) matrixMulti(R,A);
        matrixMulti(A,A);
        n>>=1;
    }
}
int main()
{

    long long res;
    int m,n;
    scanf("%d%d",&m,&n);
    trie_s=1;
    char str[16];
    while(m--)
    {
        scanf("%s",str);
        insert(str);
    }
    getFail();
    getPreMatrix();
    getResMatrix(n);
    res=0;
    for(int i=1;i<=trie_s;i++)
    {
        res=(res+R[1][i])%MOD;
    }
    printf("%lld\n",res);
    return 0;
}

以下是在转移时强行判断是否可以转移的代码

数组多叉树

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=110;
long long A[MAXN][MAXN],R[MAXN][MAXN];
const long long MOD=100000l;
struct Node
{
    int fail;
    int next[4];
    bool virus;
};
int index(char c)
{
    switch(c)
    {
        case 'A':return 0;
        case 'C':return 1;
        case 'G':return 2;
        case 'T':return 3;
    }
}
Node trie[MAXN];
int trie_s;
void insert(char *str)
{
    int len=strlen(str);
    int p=1;
    for(int i=0;i<len;i++)
    {
        int pos=index(str[i]);
        if(!trie[p].next[pos]) trie[p].next[pos]=++trie_s;
        p=trie[p].next[pos];
    }
    trie[p].virus=true;
}
void getFail()
{
    int p=1,son,temp,curr;
    queue<int> que;
    que.push(p);
    while(!que.empty())
    {
        curr=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            son=trie[curr].next[i];
            if(son)
            {
                if(curr==1) trie[son].fail=1;
                else
                {
                    temp=trie[curr].fail;
                    while(temp)
                    {
                        if(trie[temp].next[i])
                        {
                            trie[son].fail=trie[temp].next[i];
                            break;
                        }
                        temp=trie[temp].fail;
                    }
                    if(temp==0) trie[son].fail=1;
                    if(temp&&trie[trie[son].fail].virus) trie[son].virus=true;
                    //如果转移的地方是病毒,那么原来的位置也是病毒;比如BC是病毒,有一个序列为ABCDEF,那么ABCDEF中C的转移指向BC中的C,但BC是病毒结尾,那么ABCDEF也是病毒
                }
                que.push(son);
            }
        }
    }
}
void getPreMatrix()
{
    int son,temp;
    for(int i=1;i<=trie_s;i++)
    {
        if(trie[i].virus) continue;
        for(int j=0;j<4;j++)
        {
            son=trie[i].next[j];
            if(son&&!trie[son].virus) A[i][son]++;
            else if(!son)
            {
                if(i==1) A[1][1]++;
                else
                {
                    temp=i;
                    while(!trie[temp].next[j]&&temp!=1) temp=trie[temp].fail;
                    if(trie[temp].next[j]&&!trie[trie[temp].next[j]].virus) A[i][trie[temp].next[j]]++;
                    else if(!trie[temp].next[j]&&temp==1) A[i][1]++;
                }
            }
        }
    }
}
void matrixMulti(long long a[MAXN][MAXN],long long b[MAXN][MAXN])
{
    long long c[MAXN][MAXN];
    memset(c,0,sizeof(c));
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            for(int k=1;k<=trie_s;k++)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            a[i][j]=c[i][j];
        }
    }
}
void getResMatrix(int n)
{
    memset(R,0,sizeof(R));
    for(int i=1;i<=trie_s;i++)
    {
        R[i][i]=1;
    }
    while(n)
    {
        if(n&1) matrixMulti(R,A);
        matrixMulti(A,A);
        n>>=1;
    }
}
int main()
{

    long long res;
    int m,n;
    scanf("%d%d",&m,&n);
    trie_s=1;
    char str[16];
    while(m--)
    {
        scanf("%s",str);
        insert(str);
    }
    getFail();
    getPreMatrix();
    getResMatrix(n);
    res=0;
    for(int i=1;i<=trie_s;i++)
    {
        res=(res+R[1][i])%MOD;
    }
    printf("%lld\n",res);
    return 0;
}

指针多叉树

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=110;
long long A[MAXN][MAXN],R[MAXN][MAXN];
const long long MOD=100000l;
struct Node
{
    int num;
    Node *fail;
    Node *next[4];
    bool virus;
    void init()
    {
        fail=NULL;
        memset(next,NULL,sizeof(next));
        virus=false;
    }
};
Node *root;
int trie_s;
int index(char c)
{
    switch(c)
    {
        case 'A':return 0;
        case 'C':return 1;
        case 'G':return 2;
        case 'T':return 3;
    }
}
void insert(char *str)
{
    int len=strlen(str);
    Node *p=root;
    for(int i=0;i<len;i++)
    {
        int pos=index(str[i]);
        if(p->next[pos]==NULL)
        {
            p->next[pos]=new Node();
            p->next[pos]->init();
            p->next[pos]->num=++trie_s;
        }
        p=p->next[pos];
    }
    p->virus=true;
}
void getFail()
{
    Node *p=root,*son,*temp;
    queue<Node *>que;
    que.push(p);
    while(!que.empty())
    {
        Node *curr=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            son=curr->next[i];
            if(son!=NULL)
            {
                if(curr==root) son->fail=root;
                else
                {
                    temp=curr->fail;
                    while(temp!=NULL)
                    {
                        if(temp->next[i]!=NULL)
                        {
                            son->fail=temp->next[i];
                            break;
                        }
                        temp=temp->fail;
                    }
                    if(temp==NULL) son->fail=root;
                    if(temp!=NULL&&son->fail->virus) son->virus=true;
                }
                que.push(son);
            }
        }
    }
}
void getPreMatrix()
{
    Node *p=root,*son,*temp;
    queue<Node *>que;
    que.push(p);
    while(!que.empty())
    {
        Node *curr=que.front();
        que.pop();
        if(curr->virus) continue;
        for(int i=0;i<4;i++)
        {
            son=curr->next[i];
            if(son!=NULL&&!son->virus)
            {
                A[curr->num][son->num]++;
            }
            else if(son==NULL)
            {
                if(curr==root) A[1][1]++;
                else
                {
                    temp=curr;
                    while(temp->next[i]==NULL&&temp!=root) temp=temp->fail;
                    if(temp->next[i]&&!temp->next[i]->virus) A[curr->num][temp->next[i]->num]++;
                    else if(temp->next[i]==NULL&&temp==root) A[curr->num][1]++;
                }
            }
            if(son!=NULL) que.push(son);
        }
    }
}
void matrixMulti(long long a[MAXN][MAXN],long long b[MAXN][MAXN])
{
    long long c[MAXN][MAXN];
    memset(c,0,sizeof(c));
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            for(int k=1;k<=trie_s;k++)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            a[i][j]=c[i][j];
        }
    }
}
void getResMatrix(int n)
{
    memset(R,0,sizeof(R));
    for(int i=1;i<=trie_s;i++)
    {
        R[i][i]=1;
    }
    while(n)
    {
        if(n&1) matrixMulti(R,A);
        matrixMulti(A,A);
        n>>=1;
    }
}
int main()
{
    long long res;
    int m,n;
    scanf("%d%d",&m,&n);
    root=new Node();
    root->init();
    root->num=1;
    trie_s=1;
    char str[16];
    while(m--)
    {
        scanf("%s",str);
        insert(str);
    }
    getFail();
    getPreMatrix();
    getResMatrix(n);
    res=0;
    for(int i=1;i<=trie_s;i++)
    {
        res=(res+R[1][i])%MOD;
    }
    printf("%lld\n",res);
    return 0;
}

考研路茫茫——单词情结
题意:
给出n个单词词根,求出长度为1-L的所有由小写字母组成的并且至少包含一个单词词根的数目
题解:
　　因为题目要求的是至少包含一个词根的单词数目,所以我们容易想到它的反面,即一个词根也不包含单词数目;
　　设长度为len的单词中,一个词根也不包含的单词数目为sum,容易知道,sum的求法和上面的DNS序列那道题类似,即sum=Alen;而长度为len的总的单词数目为26len;
　　所以结果为26len-Alen;则最后的结果为26+262+......+26len-(A+A2+...+Alen);这里涉及到等比矩阵求和

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<iostream>
typedef unsigned long long ULL;
using namespace std;
const int MAXN=35;
int trie_s;
struct Matrix
{
    ULL arr[MAXN][MAXN];
    void init()
    {
        memset(arr,0,sizeof(arr));
        for(int i=1;i<=trie_s;i++)
        {
            arr[i][i]=1;
        }
    }
}A,R;
Matrix add(Matrix a,Matrix b)
{
    Matrix c;
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            c.arr[i][j]=a.arr[i][j]+b.arr[i][j];
        }
    }
    return c;
}
Matrix multi(Matrix a,Matrix b)
{
    Matrix c;
    memset(c.arr,0,sizeof(c));
    for(int i=1;i<=trie_s;i++)
    {
        for(int j=1;j<=trie_s;j++)
        {
            for(int k=1;k<=trie_s;k++)
            {
                c.arr[i][j]+=a.arr[i][k]*b.arr[k][j];
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,int b)
{
    Matrix res;
    res.init();
    while(b)
    {
        if(b&1) res=multi(res,a);
        a=multi(a,a);
        b>>=1;
    }
    return res;
}
Matrix sum(Matrix a,int n)
{
    if(n==1) return a;
    Matrix tmp;
    tmp.init();
    tmp=add(tmp,pow(a,n>>1));
    tmp=multi(tmp,sum(a,n>>1));
    if(n&1) tmp=add(tmp,pow(a,n));
    return tmp;
}
struct Node
{
    int fail;
    int next[26];
    bool ed;
    void init()
    {
        fail=0;
        ed=false;
        memset(next,0,sizeof(next));
    }
};
Node trie[MAXN];
void insert(char *str)
{
    int len=strlen(str);
    int p=1;
    for(int i=0;i<len;i++)
    {
        int pos=str[i]-'a';
        if(!trie[p].next[pos])
        {
            trie[p].next[pos]=++trie_s;
            trie[trie[p].next[pos]].init();
        }
        p=trie[p].next[pos];
    }
    trie[p].ed=true;
}
void getFail()
{
    queue<int> que;
    int p=1,son,temp;
    que.push(p);
    while(!que.empty())
    {
        int curr=que.front();
        que.pop();
        for(int i=0;i<26;i++)
        {
            son=trie[curr].next[i];
            if(son)
            {
                if(curr==1) trie[son].fail=1;
                else
                {
                    temp=trie[curr].fail;
                    while(temp!=0)
                    {
                        if(trie[temp].next[i])
                        {
                            trie[son].fail=trie[temp].next[i];
                            break;
                        }
                        temp=trie[temp].fail;
                    }
                    if(!temp) trie[son].fail=1;
                    if(temp&&trie[trie[son].fail].ed) trie[son].ed=true;
                }
                que.push(son);
            }
        }
    }
}
void getPreMatrix()
{
    memset(A.arr,0,sizeof(A.arr));
    int temp,son;
    for(int i=1;i<=trie_s;i++)
    {
        if(trie[i].ed) continue;
        for(int j=0;j<26;j++)
        {
            son=trie[i].next[j];
            if(son&&!trie[son].ed) A.arr[i][son]++;
            else if(!son)
            {
                if(i==1) A.arr[1][1]++;
                else
                {
                    temp=i;
                    while(!trie[temp].next[j]&&temp!=1) temp=trie[temp].fail;
                    if(trie[temp].next[j]&&!trie[trie[temp].next[j]].ed) A.arr[i][trie[temp].next[j]]++;
                    else if(!trie[temp].next[j]&&temp==1)
                    {
                        A.arr[i][1]++;
                    }
                }
            }
        }
    }
}
ULL pow(ULL a,int n)
{
    ULL res=1;
    while(n)
    {
        if(n&1) res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}
ULL powSum(ULL a,int n)
{
    if(n==1) return a;
    ULL res=(1+pow(a,n>>1))*powSum(a,n>>1);
    if(n&1) res=res+pow(a,n);
    return res;
}
int main()
{
    int n,l;
    char str[10];
    while(scanf("%d%d",&n,&l)!=EOF)
    {
        trie_s=1;
        trie[1].init();
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            insert(str);
        }
        getFail();
        getPreMatrix();
        A=sum(A,l);
        ULL total=powSum(26,l);
        ULL res=0;
        for(int i=1;i<=trie_s;i++)
        {
            res+=A.arr[1][i];
        }
        cout<<total-res<<endl;
    }
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,607评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,047评论 2赞 379
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,496评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,405评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,400评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,479评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,883评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,535评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,743评论 1赞 295
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,544评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,612评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,309评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,881评论 3赞 306
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,891评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,136评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,783评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,316评论 2赞 342

推荐阅读更多精彩内容