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.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.Output
An integer, the number of DNA sequences, mod 100000.Sample Input
4 3 AT AC AG AA
Sample Output
36
/** poj 2778 AC自動機與矩陣連乘 題目大意:給定一些模式串,問可以構造出多少中長度為n且不含模式串中的任何一個作為子串的字符串 解題思路:構造自動機,寫出狀態轉移的矩陣,進行矩陣快速冪,其n次冪就表示長度為n。然後mat[0][i]就表示從根節點到狀態點i長度為n的字符串有多少種 */ #include#include #include #include #include using namespace std; const int MOD=100000; struct Matrix { int mat[110][110],n; Matrix() {} Matrix(int _n) { n=_n; for(int i=0; i Q; for(int i=0; i<4; i++) { if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } } while(!Q.empty()) { int now=Q.front(); Q.pop(); if(end[fail[now]]==1) end[now]=1; for(int i=0; i<4; i++) { if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } } Matrix getMatrix() { Matrix res=Matrix(L); for(int i=0; i >=1; } return ret; } int main() { int n,m; while(~scanf(%d%d,&n,&m)) { ac.init(); for(int i=0;i