开心六月综合激情婷婷|欧美精品成人动漫二区|国产中文字幕综合色|亚洲人在线成视频

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，F(xiàn)or 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 3ATACAGAA

Sample Output

36

?

題意：

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

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

?

題解：

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

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

?

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

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

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

?

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

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

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

?

為什么可以這樣做？

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

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

?

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

相當(dāng)于字典樹就是一個有向圖，你就沿著它的方向跑下去。每跑m路程就會有一個對應(yīng)DNA序列，又因為你已經(jīng)把病毒串終止位置標(biāo)記了，所以根本不可能跑到那個位置。所以你跑出來的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;  //病毒串終點要標(biāo)記 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這個點給標(biāo)記了 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.icode9.com/content-4-595901.html