【题意】：给定你m个病毒串，求长度为n的不包含任意一个病毒串的种数。
【题解】：用ac自动机构造一个DFA（既有确定性的状态转移图），然后用矩阵快速幂求解。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define ll long long
6 const ll MOD = 100000;
7 const int kind = 4;
8 const int maxn = 500;
9 #define MAX 105
10 int root, tot;
11 int n, m;
12 int que[maxn], head, tail;
13 bool visit[maxn];
14 struct Node {
15 int child[kind];
16 int fail;
17 int end;
18 void init() {
19 memset(child, 0, sizeof(child));
20 fail = -1, end = 0;
21 }
22 } T[maxn];
23
24 void init() {
25 root = tot = 0;
26 T[root].init();
27 }
28
29 int hash(char ch) {
30 if(ch == 'A') return 0;
31 else if(ch == 'C') return 1;
32 else if(ch == 'G') return 2;
33 else return 3;
34 }
35
36 void insert(char *s) {//插入单词
37 int p = root, index;
38 while (*s) {
39 index = hash(*s);
40 if (!T[p].child[index]) {
41 T[++tot].init();
42 T[p].child[index] = tot;
43 }
44 p = T[p].child[index];
45 s++;
46 }
47 T[p].end = 1;
48 }
49
50 void build_ac_auto() {
51 head = tail = 0;
52 que[tail++] = root;
53 while (head < tail) {
54 int u = que[head++];
55 for (int i = 0; i < kind; i++) {
56 if (T[u].child[i]) {
57 int son = T[u].child[i];
58 int p = T[u].fail;
59 if (u == root) T[son].fail = root;
60 else {
61 T[son].fail = T[p].child[i];
62 T[son].end |= T[T[son].fail].end;
63 }
64 que[tail++] = son;
65 } else {//trie图，设定虚拟节点
66 int p = T[u].fail;
67 if (u == root) T[u].child[i] = root;
68 else T[u].child[i] = T[p].child[i];
69 }
70 }
71 }
72 }
73
74 struct Mat {
75 ll val[MAX][MAX];
76 void unit() {
77 zero();
78 for(int i = 0; i < MAX; i++) val[i][i] = 1;
79 }
80 void zero() {
81 memset(val, 0, sizeof(val));
82 }
83 }x;
84
85 Mat operator *(const Mat &a, const Mat &b) {
86 Mat tmp;
87 tmp.zero();
88 for(int k = 0; k <= tot; k++) {
89 for(int i = 0; i <= tot; i++) {
90 if(a.val[i][k])
91 for(int j = 0; j <= tot; j++) {
92 tmp.val[i][j] += a.val[i][k] * b.val[k][j];
93 if(tmp.val[i][j] >= MOD) tmp.val[i][j] %= MOD;
94 }
95 }
96 }
97 return tmp;
98 }
99
100 Mat operator ^(Mat x, int n) {
101 Mat tmp;
102 tmp.unit();
103 while(n) {
104 if(n & 1) tmp = tmp * x;
105 x = x * x;
106 n >>= 1;
107 }
108 return tmp;
109 }
110
111 void dfs(int u) {
112 visit[u] = true;
113 for(int i = 0; i < kind; i++) {
114 int v = T[u].child[i];
115 if(!T[v].end) {
116 x.val[u][v]++;
117 if(!visit[v]) dfs(v);
118 }
119 }
120 }
121
122 int main() {
123 char s[15];
124 while(~scanf("%d%d", &m, &n)) {
125 init();
126 for(int i = 0; i < m; i++) {
127 scanf("%s", s);
128 insert(s);
129 }
130 build_ac_auto();
131 x.zero();
132 memset(visit, false, sizeof(visit));
133 dfs(root);
134 Mat ans = x ^ n;
135 ll res = 0;
136 for(int i = 0; i <= tot; i++)
137 res += ans.val[0][i];
138 printf("%lld\n", res % MOD);
139 }
140 return 0;
141 }