poj 2778 AC自动机+DP+矩阵快速幂(一)

#include 
 
 #include 
 
 #include 
 
 #include 
 
 using namespace std; 
 
 typedef __int64 type; 
 
 const int kind=4;  //每个节点的子节点的个数上限 
 
 const int mod = 100000; 
 
 const int size=109; //转移矩阵的行大小 
 
 class AC_auto 
 
 { 
 
     public: 
 
     int tot; 
 
     type Mar[size][size],ans[size][size]; 
 
  
 
     struct Node 
 
     { 
 
         int key,cnt; 
 
         struct Node *next[kind],*fail; 
 
         Node() 
 
         { 
 
             key=0; 
 
             for(int i=0;i             next[i]=0; 
 
         } 
 
     }*root,node[size]; 
 
  
 
     inline Node * new_Node() 
 
     { 
 
         Node *p=&node[tot];  //静态方式，可以改为动态方式 new Node() 
 
         p->cnt=tot; 
 
         p->key=0;  //表示本节点是不是单词的结尾 
 
         memset(p->next,0,sizeof(p->next)); 
 
         tot++; 
 
         return p; 
 
     } 
 
  
 
     AC_auto(){  tot=0,root=new_Node(); } 
 
  
 
     int Index(char c) 
 
     { 
 
         switch(c) 
 
         { 
 
             case 'A':return 0; 
 
             case 'C':return 1; 
 
             case 'G':return 2; 
 
             case 'T':return 3; 
 
         } 
 
     } 
 
     void insert(char *s)//构造字典树 
 
     { 
 
         int i=0; 
 
         Node *p=root; 
 
         while(s[i]) 
 
         { 
 
             if(p->next[Index(s[i])]==0) 
 
             { 
 
                 p->next[Index(s[i])]=new_Node(); 
 
             } 
 
             p=p->next[Index(s[i])]; 
 
             i++; 
 
         } 
 
         p->key++; 
 
     } 
 
  
 





     void build_fail() 
 
     { 
 
         root->fail=root; 
 
         queue q; 
 
         q.push(root); 
 
         while(!q.empty()) 
 
         { 
 
             Node *t=q.front();q.pop(); 
 
             Node *p=0; 
 
             for(int i=0;i             { 
 
                 if(t->next[i]!=0) 
 
                 { 
 
                     if(t==root)  t->next[i]->fail = root; 
 
                     else 
 
                     { 
 
                         p=t->fail; //从父节点的失败指针开始 
 
                         while(p!=root&&p->next[i]==0) p=p->fail;//循环失败指针，一直搜索非根节点有相同索引的节点 
 
                         if(p->next[i])   t->next[i]->fail=p->next[i]; //找到，失败指针指向它 
 
                         else  t->next[i]->fail=root;  //无相同索引，失败指针指向根节点 
 
                     } 
 
                     if(t->next[i]->fail->key!=0)  t->next[i]->key++; 
 
                     q.push(t->next[i]); 
 
                 } 
 
                 else 
 
                 { 
 
                     if(t==root) t->next[i]=root;//如果根节点无此索引，失败指针指向根，表示此状态可以转换为根所代表的状态 
 
                     t->next[i]=t->fail->next[i]; 
 
                 } 
 
             } 
 
         } 
 
     } 
 
     void get_Mar() 
 
     { 
 
         memset(Mar,0,sizeof(Mar)); 
 
         for(int i=0;i         if(node[i].key==0) 
 
         { 
 
             for(int j=0;j             { 
 
                 if(node[i].next[j]->key==0) 
 
                 { 
 
                     Mar[i][node[i].next[j]->cnt]++; 
 
                 } 
 
             } 
 
         } 
 
     } 
 
     void MatrixMultiply(type b[][size], type c[][size], int sz)//矩阵乘 
 
     { 
 
         int i,j,k; 
 
         type temp[size][size] = {0}; 
 
         for (i=0; i         { 
 
             for (j=0; j             { 
 
                 for (k=0; k                 { 
 
                     temp[i][j] += b[i][k]*c[k][j]; 
 
                     if (temp[i][j]>=mod) 
 
                         temp[i][j] %= mod; 
 
                 } 
 
             } 
 
         } 
 
         for (i=0; i         { 
 
             for (