1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <queue>  5 using namespace std;  6   7 #define MAXN 105  8 #define NXTN 4  9  10 char str[15]; 11  12 typedef struct Matrix { 13     int n; 14     __int64 map[MAXN][MAXN]; 15     Matrix() {} 16     Matrix(int nn) { 17         n = nn; 18         for (int i=0; i<nn; ++i) 19             for (int j=0; j<nn; ++j) 20                 map[i][j] = 0; 21     } 22 } Matrix; 23  24 int getval(char ch) { 25     switch (ch) { 26     case ‘A‘: return 0; 27     case ‘C‘: return 1; 28     case ‘T‘: return 2; 29     case ‘G‘: return 3; 30     default: return 0; 31     } 32 } 33  34 struct AC { 35     int next[MAXN][NXTN], fail[MAXN], v[MAXN]; 36     int n, root; 37     void init() { 38         n = 0; 39         root = newNode(); 40     } 41     int newNode() { 42         fail[n] = 0; 43         v[n] = 0; 44         memset(next[n], -1, sizeof(next[n])); 45         return n++; 46     } 47     void create(char s[]) { 48         int i = 0, id; 49         int cur = root; 50  51         while (s[i]) { 52             id = getval(s[i]); 53             ++i; 54             if (next[cur][id] == -1) 55                 next[cur][id] = newNode(); 56             cur = next[cur][id]; 57         } 58         v[cur] = 1; 59     } 60     void build() { 61         int i, cur; 62         queue<int> Q; 63  64         fail[root] = root; 65         for (i=0; i<NXTN; ++i) { 66             if (next[root][i] == -1) 67                 next[root][i] = root; 68             else { 69                 fail[next[root][i]] = root; 70                 Q.push(next[root][i]); 71             } 72         } 73  74         while (!Q.empty()) { 75             cur = Q.front(); 76             Q.pop(); 77             if (v[fail[cur]])    // important 78                 v[cur] = 1; 79             for (i=0; i<NXTN; ++i) { 80                 if (next[cur][i] == -1) 81                     next[cur][i] = next[fail[cur]][i]; 82                 else { 83                     fail[next[cur][i]] = next[fail[cur]][i]; 84                     Q.push(next[cur][i]); 85                 } 86             } 87         } 88     } 89     Matrix query() { 90         int i, j; 91  92         Matrix mat(n); 93  94         for (i=0; i<n; ++i) { 95             for (j=0; j<NXTN; ++j) { 96                 if (v[next[i][j]] == 0) 97                     ++mat.map[i][next[i][j]]; 98             } 99         }100         return mat;101     }102 };103 104 AC ac;105 106 Matrix mmul(Matrix a, Matrix b) {107     int i, j, k, n = a.n;108     Matrix ret(n);109 110     for (i=0; i<n; ++i)111         for (j=0; j<n; ++j)112             for (k=0; k<n; ++k) {113                 ret.map[i][j] += a.map[i][k]*b.map[k][j];114                 ret.map[i][j] %= 100000;115             }116     return ret;117 }118 119 void mpow(Matrix a, int n) {120     Matrix ret(a.n);121     int i;122     __int64 ans;123 124     for (i=0; i<ret.n; ++i)125         ret.map[i][i] = 1;126 127     while (n) {128         if (n & 1)129             ret = mmul(ret, a);130         a = mmul(a, a);131         n >>= 1;132     }133 134     ans = 0;135     for (i=0; i<ret.n; ++i) {136         //printf("i:%I64d\n", ret.map[0][i]);137         ans += ret.map[0][i];138         ans %= 100000;139     }140     printf("%I64d\n", ans);141 }142 143 int main() {144     int m, n;145     int i;146 147     while (scanf("%d %d", &m, &n) != EOF) {148         ac.init();149         for (i=0; i<m; ++i) {150             scanf("%s", str);151             ac.create(str);152         }153         ac.build();154         Matrix mat = ac.query();155         //printf("mat.n=%d\n", mat.n);156         mpow(mat, n);157     }158 159     return 0;160 }