POJ 2778 DNA Sequence [AC自动机矩阵乘法]

DNA Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 15797		Accepted: 6095

Description

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.

Input

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.

Sample Input

4 3
AT
AC
AG
AA

Sample Output

Source

POJ Monthly--2006.03.26,dodo

题意：和那些一样：

给出p个模式串，求有多少个长度为m的字符串，其中不包含任何一个模式串为子串

一看n辣么大当然要矩阵乘法掉啦

然后观察这个套路DP方程 f[i+1][p]=sigma{f[i][j]:j能转移到p}

满足矩阵乘法的要求嘛，建矩阵就行了

如果把AC自动机当作有向图，就成了经典的图的路径方案数问题了啊

答案最后还要统计0到0的方案数哦，因为那些没有的都是0到0啦

PS：我能把这个模数写错真是绝了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=105,MOD=100000;
int m,n,mp[300];
char s[15];
struct node{
    int ch[5],val,fail;
}t[N];
int sz;
void ins(char s[]){
    //printf("ins
");
    int u=0,n=strlen(s+1);
    for(int i=1;i<=n;i++){
        int c=mp[s[i]];
        if(!t[u].ch[c]) t[u].ch[c]=++sz;
        u=t[u].ch[c];
    }
    t[u].val=1;
}
int q[N],head,tail;
void getAC(){
    head=tail=1;
    for(int i=1;i<=4;i++) if(t[0].ch[i]) q[tail++]=t[0].ch[i];
    while(head!=tail){
        int u=q[head++];
        t[u].val|=t[t[u].fail].val;
        for(int i=1;i<=4;i++){
            int &v=t[u].ch[i];
            if(!v) v=t[t[u].fail].ch[i];
            else{
                t[v].fail=t[t[u].fail].ch[i];
                q[tail++]=v;
            }
        }
    }
}
struct Matrix{
    ll z[N][N];
    Matrix(){memset(z,0,sizeof(z));}
    void ini(){for(int i=0;i<=sz;i++) z[i][i]=1;}
    void print(){
        puts("");
        for(int i=0;i<=sz;i++)
            for(int j=0;j<=sz;j++) printf("%lld%c",z[i][j],j==n?'
':' ');
        puts("");
    }
}G;
Matrix operator *(Matrix A,Matrix B){
    Matrix C;
    for(int k=0;k<=sz;k++)
        for(int i=0;i<=sz;i++) if(A.z[i][k])
            for(int j=0;j<=sz;j++) if(B.z[k][j])
                C.z[i][j]=(C.z[i][j]+A.z[i][k]*B.z[k][j])%MOD;
    return C;
}
Matrix operator ^(Matrix A,int b){
    Matrix re;re.ini();
    for(;b;b>>=1,A=A*A)
        if(b&1) re=re*A;
    return re;
}

void build(){
    for(int i=0;i<=sz;i++) if(!t[i].val){//printf("hi %d
",i);
        for(int k=1;k<=4;k++) if(!t[t[i].ch[k]].val)
            G.z[i][t[i].ch[k]]++;//,printf("k %d %d
",k,t[i].ch[k]);
    }
}
int ans;
int main(){
    freopen("in","r",stdin);
    mp['A']=1;mp['T']=2;mp['C']=3;mp['G']=4;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++) scanf("%s",s+1),ins(s);
    getAC();
    build();//G.print();
    G=G^n;
    for(int i=0;i<=sz;i++) ans=(ans+G.z[0][i])%MOD;
    printf("%d",ans);
}

POJ 2778 DNA Sequence [AC自动机 矩阵乘法]

POJ 2778 DNA Sequence [AC自动机矩阵乘法]