DNA Sequence POJ - 2778 AC自動機 && 矩陣快速冪

印度阿三17 2019-12-12

展開全文

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

題意：

多組輸入，n代表下面有n個模式串。m代表你要構造的DNA序列長度

題目讓你求DNA序列為m，序列中不出現以上n個模式串的DNA序列有多少

題解：

我的上一代碼用的我自己寫的矩陣快速冪，那個版本每次都要初始化數組，太耗時了就TLE。找了個結構體版本的快速冪

這一道題就是問你你能找到多少個長度最長為m的正常DNA序列(什么叫正常？就是不含病毒的那種)
對于矩陣(這里以2*2為例)
|X(11) X(12)|
|X(21) X(22)|
我們設我們構造的矩陣為ans，其中ans[i][j]表示DNA序列中從i節(jié)點到j節(jié)點（下面都直接稱為i、j）走一步的方法數(就是最后找出來的DNA序列中第i個位置和第j個
個位置,因為是一步，所以i和j在DNA序列中是相鄰的?？梢詷嫵烧NA的方法數)

什么叫i、j節(jié)點，我們在構造字典樹的過程中會產生節(jié)點，那個節(jié)點是第幾個產生的，那個就是它的序號

然后矩陣的二次方的ans[i][j]的意思就是從DNA序列中從i先到一個中轉點再到j有多少種DNA序列滿足
那么矩陣的n次方的ans[i][j]意思就是DNA序列中從i到n個中轉點再到j有多少種DNA序列滿足

那么我們只需要求出來ans[i][j]DNA序列中從i走一步的j這一段在DNA序列中方案數
然后這個矩陣求m次方就可以了

ans[i][j]DNA序列中從i走一步的j這一段在DNA序列中方案數的這個ans矩陣怎么求？

把每一個病毒串的終止位置給標記了，在字典樹上通過失敗指針跳轉如果能到病毒串終止位置也要把這個點標記了，然后沿著字典樹的next數組跑一邊就完了(具體看代碼)

然后第一行ans[0][1],ans[0][1]...ans[0][99]的所有數的和就可以了
ans[0][1]的意思就是從DNA序列0號位置(即，開頭)經過m-1個中轉點到1號節(jié)點 //0號位置是字典樹根的位置，所以不算在DNA序列內
這個樣子加起來就是答案

為什么可以這樣做？

ans[i][j]最初的一步矩陣：

他就代表i這個點后面可以往j這個位置走一步有多少種不重復走法

ans[i][j]的m次方矩陣：

相當于字典樹就是一個有向圖，你就沿著它的方向跑下去。每跑m路程就會有一個對應DNA序列，又因為你已經把病毒串終止位置標記了，所以根本不可能跑到那個位置。所以你跑出來的DNA序列中也不會包含病毒序列

代碼：

  1 #include<stdio.h>  
  2 #include<iostream>
  3 #include<string.h>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 const int maxn=115;
  8 const int N=4;
  9 const int mod=100000;
 10 typedef long long ll;
 11 int n,m;
 12 int w[120];
 13 struct Matrix
 14 {
 15     int mat[maxn][maxn],n;
 16     Matrix() {}
 17     Matrix(int _n)
 18     {
 19         n = _n;
 20         for(int i=0; i<n; i  )
 21             for(int j=0; j<n; j  )
 22                 mat[i][j]=0;
 23     }
 24     Matrix operator *(const Matrix &b)const
 25     {
 26         Matrix ret=Matrix(n);
 27         for(int i=0; i<n; i  )
 28             for(int j=0; j<n; j  )
 29                 for(int k=0; k<n; k  )
 30                 {
 31                     int tmp=(long long)mat[i][k]*b.mat[k][j]%mod;
 32                     ret.mat[i][j]=(ret.mat[i][j] tmp)%mod;
 33                 }
 34         return ret;
 35     }
 36 };
 37 struct Trie
 38 {
 39     int next[maxn][N],fail[maxn],ends[maxn];
 40     int root,L;
 41     int New_node() //創(chuàng)建一個新節(jié)點
 42     {
 43         for(int i=0; i<N;   i)
 44         {
 45             next[L][i]=-1;
 46         }
 47         ends[L  ]=0;
 48         return L-1;
 49     }
 50     void init()  //創(chuàng)建根節(jié)點
 51     {
 52         L=0;
 53         root=New_node();
 54     }
 55     void inserts(char s[])  //往字典樹里面插入新字符串
 56     {
 57         int len=strlen(s);
 58         int now=root;
 59         for(int i=0; i<len;   i)
 60         {
 61             if(next[now][w[s[i]]]==-1)
 62                 next[now][w[s[i]]]=New_node();
 63             now=next[now][w[s[i]]];
 64         }
 65         ends[now]=1;  //病毒串終點要標記
 66     }
 67     void build()
 68     {
 69         queue<int>r;
 70         fail[root]=root;
 71         for(int i=0; i<N;   i)
 72         {
 73             if(next[root][i]==-1)
 74             {
 75                 next[root][i]=root;
 76             }
 77             else
 78             {
 79                 fail[next[root][i]]=root;
 80                 r.push(next[root][i]);
 81             }
 82         }
 83         while(!r.empty())
 84         {
 85             int now=r.front();
 86             r.pop();
 87             if(ends[fail[now]])  //如果now節(jié)點的失敗指針指向病毒串終點，那么也要把now這個點給標記了
 88             {
 89                 ends[now]=1;
 90             }
 91             for(int i=0; i<N;   i)
 92             {
 93                 if(next[now][i]==-1)
 94                 {
 95                     next[now][i]=next[fail[now]][i];  
 96                 }
 97                 else
 98                 {
 99                     fail[next[now][i]]=next[fail[now]][i]; 
100                     r.push(next[now][i]);
101                 }
102             }
103         }
104     }
105     Matrix Build_c()
106     {
107         Matrix res=Matrix(L);
108         for(int i=0; i<L;   i)
109         {
110             for(int j=0; j<N;   j)
111             {
112                 if(ends[next[i][j]]==0)  //創(chuàng)建走一步的ans矩陣
113                 {
114                     res.mat[i][next[i][j]]  ;
115                 }
116             }
117         }
118         return res;
119     }
120 };
121 char s[20];
122 Trie ac;
123 Matrix pow_M(Matrix a,int n)
124 {
125     Matrix ret = Matrix(a.n);
126     for(int i = 0; i < ret.n; i  )
127         ret.mat[i][i]=1;
128     Matrix tmp=a;
129     while(n)
130     {
131         if(n&1)ret=ret*tmp;
132         tmp=tmp*tmp;
133         n>>=1;
134     }
135     return ret;
136 }
137 int main()
138 {
139     w['A']=0;
140     w['C']=1;
141     w['G']=2;
142     w['T']=3;
143     while(~scanf("%d%d",&n,&m))
144     {
145         ac.init();
146         while(n--)
147         {
148             scanf("%s",s);
149             ac.inserts(s);
150         }
151         ac.build();
152         Matrix ans=ac.Build_c();
153         ans=pow_M(ans,m);
154         int sum=0;
155         for(int i=0; i<ac.L;   i)
156             sum =ans.mat[0][i],sum%=mod;
157         printf("%d\n",sum);
158     }
159     return 0;
160 }

來源：https://www./content-4-595901.html