【题意】:给定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, 0sizeof (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, 0sizeof(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 = *- '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 == 1return 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 == 1return 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, falsesizeof(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 }