poj 2778 AC自動機與矩陣連乘

poj 2778 AC自動機與矩陣連乘

 

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

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; iQ;
        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