本文移植自个人的原博客（原文）

题目链接

题目描述

It’s well known that DNA Sequence is a sequence only contains A, C, T and G, and it’s very useful to analyze a segment of DNA Sequence，For example, if a animal’s DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don’t contain those segments.

Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.

First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.

Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.

Output An integer, the number of DNA sequences, mod 100000.

样例

输入样例

4 3
AT
AC
AG
AA

输出样例

题解

题目大意为给定$n$个病毒串，求不包含这些病毒串且长度为$m$的资源串个数（均由A,G,C,T组成）。

这是一题比较典型的矩阵乘法与AC自动机结合的题，此处用到了一个叫做邻接矩阵的概念，即$res[i][t]$存的是从$i$到$t$恰好一步能到达的方案数（当边为双向时，该矩阵关于主对角线对称），那么当$res′=res^m$时，$res′[i][t]$表示从$i$到$t$恰好走$m$步能到达的方案数。

有了这个概念，我们就可以将AC自动机看作一棵树，每一种不同的资源串即为一种从根节点$0$
到叶节点$i$的方案。由此建立AC自动机，由于该图是一棵树，两点之间路径唯一，且只能向下走，那么$res$的初始化即为赋值$res[i][son[i]]$,但此时必然会包含所有的病毒串，那么不妨利用AC自动机的功能记录一下哪些点不能走到，然后进行初始化。需要注意的是，有些资源串虽不是病毒串，但也包含病毒串（即其$fail$指针指向病毒串），只需要传递一下即可。

刚开些写的时候，因为矩阵开的太大，导致还没进入主程序就爆栈了…后来因为取模操作过多又$TLE$了。纠结了好久为什么当该节点没有被病毒串遍历时要赋值成$tr[fail[x]][j]$，导致$res[i][son[i]]++$写成了$res[i][son[i]]=1$又挂了。（看来当时还没理解AC自动机的原理）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int  N =200+1;
const int mod =100000;
const int maxf =255;
long long n,m,tr[N][4],tot,tmp,fail[N];
int idd[N];
bool tag[N];
char s[N];
int ss[4]={'A','G','C','T'};
struct martix{long long a[N][N];}res,ans;
martix operator * (martix c,martix b)
{
    martix ret;
    memset(ret.a,0,sizeof(ret.a));
    for(int i=0;i<=tot;++i)
    for(int t=0;t<=tot;++t)
    {
        for(int k=0;k<=tot;++k)
        ret.a[i][t]+=c.a[i][k]*b.a[k][t];
        ret.a[i][t]%=mod;
    }
    return ret;
}
void init(){idd[ss[0]]=0;idd[ss[1]]=1;idd[ss[2]]=2;idd[ss[3]]=3;}
void insert(int num)
{
    int now=0;
    int n=strlen(s);
    for(int i=0;i<n;++i)
    {
        if(tr[now][idd[s[i]]]==-1)
        {
            tr[now][idd[s[i]]]=++tot;
            for(int j=0;j<4;++j)tr[tot][j]=-1;    
        //    tag[tot]=0;
        }
        now=tr[now][idd[s[i]]];
    }
    tag[now]=true;
}
void getfail()
{
    queue<int>q;fail[0]=0;
    for(int j=0;j<4;++j)
    if(tr[0][j]!=-1)q.push(tr[0][j]),fail[tr[0][j]]=0;
    else tr[0][j]=0;

    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(tag[fail[x]])tag[x]=true;
        for(int j=0;j<4;++j)
        if(tr[x][j]!=-1)fail[tr[x][j]]=tr[fail[x]][j],q.push(tr[x][j]);    
        else tr[x][j] =tr[fail[x]][j];
    }
}
void slove()
{
    for(int i=0;i<=tot;i++)
    for(int j=0;j<4;j++)
    if(!tag[i]&&!tag[tr[i][j]]) res.a[i][tr[i][j]]++;

}
int main()
{
    init();
    scanf("%d",&n);scanf("%d",&m);
    for(int i=0;i<4;++i)tr[0][i]=-1;
    for(int i=1;i<=n;++i)scanf("%s",s),insert(i);
    getfail();
    slove();
    for(int i=0;i<=tot;++i)ans.a[i][i]=1;
    if(!m){cout<<0;return 0;}
    while(m)
    {
        if(m&1) ans=ans*res;
        m/=2;
        res=res*res;
    }
    int anss=0;
    for(int i=0;i<=tot;++i)(anss+=ans.a[0][i])%=mod;
    cout<<anss;
}

POJ2778 DNA Sequence

题目链接

题目描述

样例

输入样例

输出样例

题解