背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。
于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。
比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。
这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。
于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。
比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac...aaz,
(26个)aba,abb,abc...abz,
(25个)baa,caa,daa...zaa,
(25个)bab,cab,dab...zab。
这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。
Input本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。
Output对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
Sample Input
2 3
aa ab
1 2
a
Sample Output
104
52
先找出来长度小于等于L的串，一共有多少个。然后找出来长度小于等于L的串不包含模式串有多少个
两者之差就是答案
题意：
问出现这几个模式串，长度小于等于L的字符串数量有多少
题解：
建议提前看一下DNA Sequence POJ - 2778
和DNA Sequence POJ - 2778（问不出现这几个模式串，长度等于L的字符串数量有多少） 这道题差不多。
只需要转化一下：
先求出来长度小于等于L所有串的数量，然后再求一下不出现这几个模式串，长度小于等于L的字符串数量有多少
假设用ac自动机跑出来的矩阵是A
那么就求出来A,A^1,A^2...A^L.每一个矩阵第一行之和。
这就只需要在A矩阵中增加一列，这一列都赋值为1.在对应也要把增加那一行的其他位置赋值为0
例如
原来A= | 1 2 | =>> 转化后 A= |1 2 1 |
| 3 4 | | 3 4 1 |
|0 0 1 |
这样最后跑出来的A^L的第一行所有数之和就是最后答案
至于为什么，看下面：
全部串的数量：
26^1 + 26^2 + 26^3 + … + 26^n，也用矩阵快速幂计算。f(n) = 26 * f(n - 1) + 26。
| f(n - 1) 1 |
| 0 0 |
系数矩阵：
| 26 0 |
| 26 1 |
相乘得到：
| f(n) 1 |
| 0 0 |
两者之差就是结果
代码：
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int maxn=70;
8 const int N=26;
9 const int mod=100000;
10 typedef long long ll;
11 typedef unsigned long long ull;
12 ull m;
13 struct Matrix
14 {
15 unsigned long long mat[40][40];
16 int n;
17 Matrix(){}
18 Matrix(int _n)
19 {
20 n=_n;
21 for(int i=0;i<n;i++)
22 for(int j=0;j<n;j++)
23 mat[i][j] = 0;
24 }
25 Matrix operator *(const Matrix &b)const
26 {
27 Matrix ret = Matrix(n);
28 for(int i=0;i<n;i++)
29 for(int j=0;j<n;j++)
30 for(int k=0;k<n;k++)
31 ret.mat[i][j]+=mat[i][k]*b.mat[k][j];
32 return ret;
33 }
34 };
35 unsigned long long pow_m(unsigned long long a,int n)
36 {
37 unsigned long long ret=1;
38 unsigned long long tmp = a;
39 while(n)
40 {
41 if(n&1)ret*=tmp;
42 tmp*=tmp;
43 n>>=1;
44 }
45 return ret;
46 }
47 Matrix pow_M(Matrix a,int n)
48 {
49 Matrix ret = Matrix(a.n);
50 for(int i=0;i<a.n;i++)
51 ret.mat[i][i] = 1;
52 Matrix tmp = a;
53 while(n)
54 {
55 if(n&1)ret=ret*tmp;
56 tmp=tmp*tmp;
57 n>>=1;
58 }
59 return ret;
60 }
61 struct Trie
62 {
63 ull next[maxn][N],fail[maxn],ends[maxn];
64 ull root,L;
65 ull New_node() //创建一个新节点
66 {
67 for(ull i=0; i<N; ++i)
68 {
69 next[L][i]=-1;
70 }
71 ends[L++]=0;
72 return L-1;
73 }
74 void init() //创建根节点
75 {
76 L=0;
77 root=New_node();
78 }
79 void inserts(char s[]) //往字典树里面插入新字符串
80 {
81 ull len=strlen(s);
82 ull now=root;
83 for(ull i=0; i<len; ++i)
84 {
85 if(next[now][s[i]-'a']==-1)
86 next[now][s[i]-'a']=New_node();
87 now=next[now][s[i]-'a'];
88 }
89 ends[now]=1;
90 }
91 void build()
92 {
93 queue<ull>r;
94 fail[root]=root;
95 for(ull i=0; i<N; ++i)
96 {
97 if(next[root][i]==-1)
98 {
99 next[root][i]=root;
100 }
101 else
102 {
103 fail[next[root][i]]=root;
104 r.push(next[root][i]);
105 }
106 }
107 while(!r.empty())
108 {
109 ull now=r.front();
110 r.pop();
111 if(ends[fail[now]])
112 {
113 ends[now]=1;
114 }
115 for(ull i=0; i<N; ++i)
116 {
117 if(next[now][i]==-1)
118 {
119 next[now][i]=next[fail[now]][i]; //叶节点处没有设置失败节点而是往next上接了一段，这个时候
120 //这个fail里面的值已经在下面的else里面放过东西了
121 }
122 else
123 {
124 fail[next[now][i]]=next[fail[now]][i]; //此节点的子节点的失败节点就是此节点失败节点对应字符位置
125 r.push(next[now][i]);
126 }
127 }
128 }
129 }
130 Matrix Build_c()
131 {
132 Matrix res=Matrix(L+1);
133 for(ull i=0; i<L; ++i)
134 {
135 for(ull j=0; j<N; ++j)
136 {
137 if(ends[next[i][j]]==0)
138 {
139 res.mat[i][next[i][j]]++;
140 }
141 }
142 }
143 for(ull i=0;i<L+1;++i)
144 res.mat[i][L]=1;
145 return res;
146 }
147 };
148 char s[10];
149 Trie ac;
150 Matrix pow_M(Matrix a,ull n)
151 {
152 Matrix ret = Matrix(a.n);
153 for(ull i = 0; i < ret.n; i++)
154 ret.mat[i][i]=1;
155 Matrix tmp=a;
156 while(n)
157 {
158 if(n&1)ret=ret*tmp;
159 tmp=tmp*tmp;
160 n>>=1;
161 }
162 return ret;
163 }
164 int main()
165 {
166 ull n;
167 while(~scanf("%llu%llu",&n,&m))
168 {
169 ac.init();
170 while(n--)
171 {
172 scanf("%s",s);
173 ac.inserts(s);
174 }
175 Matrix two=Matrix(2); /*求出总共有多少单词数*/
176 two.mat[0][0]=26;
177 two.mat[0][1]=1;
178 two.mat[1][1]=1;
179 two=pow_M(two,m);
180 ull tot=two.mat[0][1]*26;
181
182 ac.build(); /*求不满足题意得单词数量*/
183 Matrix ans=ac.Build_c();
184 ans=pow_M(ans,m);
185 ull sum=0;
186 for(ull i=0;i<ans.n;++i)
187 sum+=ans.mat[0][i];
188 sum--;
189
190 printf("%llu\n",tot-sum);
191 }
192 return 0;
193 }