poj 2778 DNA Sequence(ACオートマトン+マトリックス高速べき乗)

タイトルリンク:クリックしてリンクを開く
ウイルスのDNAを持つm文字列を与えます.次に、nの長さの文字列にウイルスが含まれていないことを聞いて、どれだけの可能性がありますか?すべての文字列の後にACGTといういくつかの文字列が構成されています
解題構想:ACオートマトン+マトリックス高速べき乗
前置内容:隣接行列べき乗の意味:クリックしてリンクを開く
分析:まず题意によって先に1つのACオートマチックを建てて、実はACオートマチック自身は1枚の図で、ACオートマチックの中のすべての结点は図の中の頂点に相当して、すべての転移A、C、G、Tは1本の辺に相当します;隣接行列べき乗の意味に基づいて,長さnを求める文字列の個数は,始点から図中をnステップで行ける点のスキーム数の和に相当することが分かったが,nは大きく,行列高速べき乗を用いることができる.しかし、この問題にはいくつかの文字列を持つことができないという制限があり、図の中にはいくつかのノードが通過できないという意味で、ACオートマチックのend[i]によってこのような状況を取り除くことができる.
コード:

#include 
#include 
#include 
#define MOD 100000
typedef long long ll;
using namespace std;
struct Matrix{
    ll m[110][110];
    int L;
    Matrix(int len){
        L=len;
        for(int i=0;i>1;
        a=mat(a,a);
    }
    return t;
}
struct Trie{
    int next1[110][4],fail[110];
    bool end1[110];
    int root,L;
    int newnode(){
        for(int i=0;i<4;++i) next1[L][i]=-1;
        end1[L++]=false;
        return L-1;
    }
    void init(){ L=0; root=newnode(); }
    int getchs(char ch){
        switch(ch){
        case 'A': return 0;break;
        case 'C': return 1;break;
        case 'G': return 2;break;
        case 'T': return 3;break;
        }
    }
    void insertnode(char* str){
        int now=root;
        int len=strlen(str);
        for(int i=0;i q;
        for(int i=0;i<4;++i){
            if(next1[root][i]==-1) next1[root][i]=root;
            else{
                fail[next1[root][i]]=root;
                q.push(next1[root][i]);
            }
        }
        while(!q.empty()){
            int now=q.front(); q.pop();
            if(end1[fail[now]]==true)///  
                end1[now]=true;
            for(int i=0;i<4;++i){
                if(next1[now][i]==-1) next1[now][i]=next1[fail[now]][i];
                else {
                    fail[next1[now][i]]=next1[fail[now]][i];
                    q.push(next1[now][i]);
                }
            }
        }
    }
    Matrix getMatrix(){
        Matrix res = Matrix(L);
        for(int i=0;i