POJ 2778 AC自动机

题目链接 http://poj.org/problem?id=2778
问不包含m=10个模式串的给定长度n=2000000000的串有多少个。
大体思路:用矩阵a[i][j]表示从i到j有多少种不同的路径。其中i,j是自动机上的状态。
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cctype>
  6 #include <vector>
  7 #include <bitset>
  8 #include <stack>
  9 #include <queue>
 10 #include <map>
 11 #include <algorithm>
 12 #include <iostream>
 13 #include <string>
 14 #include <set>
 15 #define X first
 16 #define Y second
 17 #define sqr(x) (x)*(x)
 18 #pragma comment(linker,"/STACK:102400000,102400000")
 19 using namespace std;
 20 const double PI = acos(-1.0);
 21 map<int, int>::iterator it;
 22 typedef long long LL ;
 23 template<typename T> void checkmin(T &x, T y) {x = min(x, y);}
 24 template<typename T> void checkmax(T &x, T y) {x = max(x, y);}
 25 
 26 const int MAX_NODE = 105;
 27 const int CHILD_NUM = 4;
 28 const LL mod = 100000;
 29 
 30 struct Matrix {
 31     LL d[MAX_NODE][MAX_NODE];
 32     int m;
 33     void Set_Zero() {
 34         memset(d, 0, sizeof(d));
 35     }
 36     void Set_One() {
 37         memset(d, 0, sizeof(d));
 38         for(int i = 0; i < m; ++i)d[i][i] = 1;
 39     }
 40     Matrix operator *(Matrix x) {
 41         Matrix ret(m);
 42         ret.Set_Zero();
 43         for(int i = 0; i < m; ++i) {
 44             for(int k = 0; k < m; ++k) {
 45                 if(!d[i][k])continue;
 46                 for(int j = 0; j < m; ++j) {
 47                     ret.d[i][j] += d[i][k] * x.d[k][j];
 48                     ret.d[i][j] %= mod;
 49                 }
 50             }
 51         }
 52         return ret;
 53     }
 54     Matrix() {}
 55     Matrix(int _n): m(_n) {}
 56     Matrix Power(LL n) {
 57         Matrix a(m), b(m);
 58         b.Set_One();
 59         a = *this;
 60         while(n) {
 61             if(n & 1)b = a * b;
 62             a = a * a;
 63             n >>= 1;
 64         }
 65         return b;
 66     }
 67     void pf() {
 68         for(int i = 0; i < m; ++i) {
 69             for(int j = 0; j < m; ++j) {
 70                 printf("%3d", d[i][j]);
 71             } puts("");
 72         }
 73     }
 74 };
 75 
 76 class ACAutomaton {
 77     public:
 78         int chd[MAX_NODE][CHILD_NUM];
 79         int flag[MAX_NODE];
 80         int fail[MAX_NODE];
 81         int Q[MAX_NODE];
 82         int ID[MAX_NODE];
 83         int sz;
 84         void Initialize() {
 85             fail[0] = 0;
 86             ID['A'] = 0;
 87             ID['C'] = 1;
 88             ID['G'] = 2;
 89             ID['T'] = 3;
 90         }
 91         void Reset() {
 92             sz = 1;
 93             memset(chd[0], -1, sizeof(chd[0]));
 94             flag[0]=0;
 95         }
 96         void Insert(char *s) {
 97             int q = 0;
 98             for(; *s; ++s) {
 99                 int c = ID[*s];
100                 if(chd[q][c] == -1) {
101                     memset(chd[sz], -1, sizeof(chd[sz]));
102                     flag[sz] = 0;
103                     chd[q][c] = sz++;
104                 }
105                 q = chd[q][c];
106             }
107             flag[q] = 1;
108         }
109         void Construct() {
110             int *s = Q, *e = Q;
111             for(int i = 0; i < CHILD_NUM; ++i) {
112                 if(~chd[0][i]) {
113                     fail[ chd[0][i] ] = 0;
114                     *e++ = chd[0][i];
115                 }
116                 else chd[0][i] = 0;
117             }
118             while(s != e) {
119                 int r = *s++;
120                 for(int i = 0; i < CHILD_NUM; ++i) {
121                     int &u = chd[r][i];
122                     int v = fail[r];
123                     if(~u) {
124                         *e++ = u;
125                         fail[u] = chd[v][i];
126                         flag[u] |= flag[ fail[u] ];
127                     }
128                     else u = chd[v][i];
129                 }
130             }
131         }
132         Matrix Get_Matrix() {
133             Matrix ret(sz);
134             ret.Set_Zero();
135             for(int i = 0; i < sz; ++i) {
136                 if(flag[i])continue;
137                 for(int j = 0; j < CHILD_NUM; ++j) {
138                     if(flag[ chd[i][j] ])continue;
139                     ++ret.d[i][ chd[i][j] ] ;
140                 }
141             }
142             return ret;
143         }
144 
145 } AC;
146 char s[13];
147 int main() {
148     int m;
149     LL n;
150     AC.Initialize();
151     while(~scanf("%d%I64d", &m, &n)) {
152         AC.Reset();
153         for(int i = 0; i < m; ++i) {
154             scanf("%s", s);
155             AC.Insert(s);
156         }
157         AC.Construct();
158         Matrix mt = AC.Get_Matrix();
159         //mt.pf();
160         mt = mt.Power(n);
161         //mt.pf();
162         LL res = 0;
163         for(int i = 0; i < AC.sz; ++i) {
164             if(!AC.flag[i])res += mt.d[0][i];
165             res %= mod;
166         }
167         printf("%I64d
", res);
168     }
169     return 0;
170 }