【题意】：给定n个词根，求长度不超过L，至少包含一个词根的字符串的数目。
【题解】：可以从对立角度来想，就是先求出所有字符串的数目，再减去不包含任一词根的字符串的数目。
字符串总数为26^1 + 26^2 + …… + 26^l。
不包含任一词根的字符串的数目：利用ac自动机构造DFA，然后得出初始矩阵A，数目即为：A^1 + A^2 + …… + A^l。
作差即为答案。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define ull unsigned long long
6 int n, l;
7 const int kind = 26;
8 const int maxn = 35;
9 int root, tot;
10 char ch[10];
11 bool visit[maxn];
12 struct Node {
13 int child[kind];
14 int fail;
15 bool id;
16 void init() {
17 memset(child, 0, sizeof (child));
18 fail = -1, id = false;
19 }
20 } T[maxn];
21
22 int que[maxn], head, tail;
23 void init() {
24 root = tot = 0;
25 T[root].init();
26 }
27
28 struct Mat {
29 ull val[maxn][maxn];
30 void unit() {//单位矩阵
31 zero();
32 for(int i = 0; i < maxn; i++) val[i][i] = 1;
33 }
34 void zero() {//零矩阵
35 memset(val, 0, sizeof(val));
36 }
37 }x;
38
39 Mat operator *(const Mat &a, const Mat &b) {//矩阵乘法
40 Mat tmp;
41 tmp.zero();
42 for(int k = 0; k <= tot; k++) {
43 for(int i = 0; i <= tot; i++)
44 if(a.val[i][k])
45 for(int j = 0; j <= tot; j++) {
46 tmp.val[i][j] += a.val[i][k] * b.val[k][j];
47 }
48 }
49 return tmp;
50 }
51
52 Mat operator ^(Mat x, int n) {//矩阵快速幂
53 Mat tmp;
54 tmp.unit();
55 while(n) {
56 if(n & 1) tmp = tmp * x;
57 x = x * x;
58 n >>= 1;
59 }
60 return tmp;
61 }
62
63 Mat operator +(const Mat &a, const Mat &b) {//矩阵加法
64 Mat tmp;
65 for(int i = 0; i <= tot; i++)
66 for(int j = 0; j <= tot; j++)
67 tmp.val[i][j] = a.val[i][j] + b.val[i][j];
68 return tmp;
69 }
70
71 void insert(char *s) {//插入单词
72 int p = root, index;
73 while (*s) {
74 index = *s - 'a';
75 if (!T[p].child[index]) {
76 T[++tot].init();
77 T[p].child[index] = tot;
78 }
79 p = T[p].child[index];
80 s++;
81 }
82 T[p].id = true;
83 }
84
85 void build_ac_auto() {
86 head = tail = 0;
87 que[tail++] = root;
88 while (head < tail) {
89 int u = que[head++];
90 for (int i = 0; i < kind; i++) {
91 if (T[u].child[i]) {
92 int son = T[u].child[i];
93 int p = T[u].fail;
94 if (u == root) T[son].fail = root;
95 else {
96 T[son].fail = T[p].child[i];
97 T[son].id |= T[T[son].fail].id;
98 }
99 que[tail++] = son;
100 } else {//trie图，设定虚拟节点
101 int p = T[u].fail;
102 if (u == root) T[u].child[i] = root;
103 else T[u].child[i] = T[p].child[i];
104 }
105 }
106 }
107 }
108
109 Mat sum(int k) {
110 if(k == 1) return x;
111 else {
112 Mat tmp = sum(k >> 1);
113 if(k & 1) {
114 Mat tmp2 = x ^ ((k >> 1) + 1);
115 return tmp + tmp2 + tmp * tmp2;
116 } else {
117 Mat tmp2 = x ^ (k >> 1);
118 return tmp + tmp * tmp2;
119 }
120 }
121 }
122
123 ull quickpower(ull x, int n) {
124 ull tmp = 1;
125 while(n) {
126 if(n & 1) tmp = x * tmp;
127 x = x * x;
128 n >>= 1;
129 }
130 return tmp;
131 }
132
133 ull sum2(ull x, int k) {
134 if(k == 1) return x;
135 ull tmp = sum2(x, k >> 1);
136 if(k & 1) {
137 ull tmp2 = quickpower(x, (k >> 1) + 1);
138 return tmp + tmp2 + tmp * tmp2;
139 } else {
140 ull tmp2 = quickpower(x, k >> 1);
141 return tmp + tmp * tmp2;
142 }
143 }
144
145 void create_Mat() {
146 x.zero();
147 for(int i = 0; i <= tot; i++)
148 if(!T[i].id)
149 for(int j = 0 ;j < kind; j++) {
150 int son = T[i].child[j];
151 if(!T[son].id)
152 x.val[i][son]++;
153 }
154 }
155
156 void solve() {
157 memset(visit, false, sizeof(visit));
158 create_Mat();
159 ull ans = sum2(26, l);
160 Mat tmp = sum(l);
161 for(int i = 0; i <= tot; i++)
162 ans -= tmp.val[0][i];
163 printf("%I64u\n", ans);
164 }
165
166 int main() {
167 while(~scanf("%d%d", &n, &l)) {
168 init();
169 for(int i = 0; i < n; i++) {
170 scanf("%s", ch);
171 insert(ch);
172 }
173 build_ac_auto();
174 solve();
175 }
176 return 0;
177 }