背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反，变坏，离去"等。
一天，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
对于所有满足的情况 = 所有情况-不满足情况
不满足情况即是不包含词根的单词，对于计算满足长度所有情况，可以联想到矩阵快速幂，这样我们就只需要建一个矩阵图
对于建图，我们知道，所有以词根作为前缀子串的都是不符合条件的。
从根开始记录每种前缀可以添加的字母路径数（字母不是词根的结尾）。
于是我们可以想到AC自动机，对于自动机补全的trie图，每个单词的fail都指向其最长子后缀
也就是从根以fail指针向下建图的话，当遍历到一个词根末尾时，其下面的有词根都时不合法的，这可以用dfs维护。
我们知道当矩阵中存有边权（代表路径数）时（相当于到每个点走一条路径），我们将自身乘自身，得到的二次幂矩阵，每个位置的权值就相当于从i走到j走两条路径的路径数目。（离散数学）
这样推广到这，就相当于算出矩阵的L次幂，其第一行的和就是从0长度到L长度经过各个路径以各种字母结尾的路径和，这是长度等于L的情况。
那么对于长度<=L的所有情况，我们知道 Σ(A1+A2+A3+...+AL)，然后其第一行的和即是答案。
一开始写的是递归，对于L=6为偶数，A1+A2+A3+A3(A1+A2+A3)
对于L=5为奇数，A1+A2+A2(A1+A2)+A5
但也许是姿势不对，一直tle。 然后看了Discus，我们可以添加一维，（假设原本矩阵为L，此L！=题面的L），使得L+1列全是1，这样对于第L个矩阵maps【1】【L+1】就储存Σ（A1+A2+A3+...+A[L-1]）
对于取模，因为是对1<<64取模，太大了直接取不了（睿智的尝试），可以直接把相关数组开成unsign long long 可以直接对溢出舍去相当于取模
还有利用等比数列公式时，由于涉及除法，利用欧拉定理求出逆元即可。 附上丑代码
#include<bits/stdc++.h>
using namespace std; typedef unsigned long long ull;
struct Node
{
int y,next;
} node[];
int cnt,head[],L;
int n;
ull len;
int tohash[],topos;
void add(int x,int y)
{
node[++cnt].y=y;
node[cnt].next=head[x];
head[x]=cnt;
} struct MAP
{
ull m[][];
friend MAP operator*(const MAP a,const MAP b)
{
MAP tmp;
for(int i=; i<=L+; i++)
{
for(int j=; j<=L+; j++)
{
tmp.m[i][j] = ; for(int k=; k<=L+; k++)
{
tmp.m[i][j] = tmp.m[i][j]+ a.m[i][k]*b.m[k][j];
} }
}
return tmp;
}
// friend MAP operator+(const MAP a,const MAP b)
// {
// MAP tmp;
// for(int i=1;i<=L;i++)
// {
// for(int j=1;j<=L+;j++)
// {
// tmp.m[i][j] = a.m[i][j] + b.m[i][j];
// }
// }
// return tmp;
// }
void init()
{
for(int i=; i<=L+; i++)
{
for(int j=; j<=L+; j++)
{
m[i][j] = ;
}
m[i][i] = ;
}
}
} maps;
struct ACTO
{
int trie[][],tot;
int dp[];
int fail[];
int End[];
void init()
{
tot = cnt = L = topos = ;
memset(trie,,sizeof(trie));
memset(maps.m,,sizeof(maps.m));
memset(head,,sizeof(head));
memset(dp,,sizeof(dp));
memset(fail,,sizeof(fail));
memset(End,,sizeof(End));
memset(tohash,,sizeof(tohash));
}
void Insert(char *str,int num)
{
int len = strlen(str),p=;
for(int i=; i<len; i++)
{
int ch = str[i]-'a';
if(!trie[p][ch])trie[p][ch]=++tot;
p = trie[p][ch];
}
End[p]=num;
}
void get_fail()
{
queue<int>que;
while(!que.empty())que.pop();
for(int i=; i<; i++)if(trie[][i])que.push(trie[][i]);
while(!que.empty())
{
int p = que.front();
que.pop();
for(int i=; i<; i++)
{
if(trie[p][i])
{
fail[trie[p][i]] = trie[fail[p]][i];
que.push(trie[p][i]);
}
else trie[p][i] = trie[fail[p]][i];
}
}
}
void make_edge()
{
for(int i=; i<=tot; i++)
{
add(fail[i],i);
}
}
void dfs(int x,int f)
{
if(End[x])f=;
dp[x] = f;
for(int i=head[x]; i; i=node[i].next)
{
dfs(node[i].y,f);
} }
void graph()
{
for(int i=; i<=tot; i++)
{
if(!dp[i])
{
L++;
if(!tohash[i])tohash[i] = ++topos;
for(int j=; j<; j++)
{
if(!dp[trie[i][j]])
{
if(!tohash[trie[i][j]])tohash[trie[i][j]]=++topos;
maps.m[tohash[i]][tohash[trie[i][j]]]++;
}
}
}
}
}
}; MAP qpow(MAP a,ull b)
{
MAP ans;
ans.init();
MAP base = a;
while(b)
{
if(b&)ans = ans*base;
base = base * base;
b >>= ;
}
return ans;
} ACTO AC; //MAP cal(int l,int r)
//{
//
// if(l==r)return maps;
// int mid = r/2;
// if(r & 1)
// {
// return cal(l,mid)+qpow(maps,mid)*cal(l,mid)+qpow(maps,r);
// }
// else
// {
// return cal(l,mid)+cal(l,mid)*qpow(maps,mid);
// }
//} ull qmulti(ull m,ull n)
{
ull ans = ;
while(n)
{
if(n&)ans += m;
m += m;
n >>= ;
}
return ans;
}
ull qpow(ull a,ull b)
{
ull ans = ;
ull base = a;
while(b)
{
if(b&)ans = qmulti(ans,base);
base = qmulti(base,base);
b >>= ;
}
return ans;
} int main()
{
while(~scanf("%d%llu",&n,&len))
{
AC.init();
memset(maps.m,,sizeof(maps));
char W[];
for(int i=; i<=n; i++)
{
scanf(" %s",W);
AC.Insert(W,i);
}
AC.get_fail();
AC.make_edge();
AC.dfs(,);
AC.graph();
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
printf(" %d ",maps.m[i][j]);
}
puts("");
}
for(int i=;i<=L+;i++)maps.m[i][L+]=;
MAP ans = qpow(maps,len);
ull total = (qpow(,len+)-)*qpow(,(1ull<<)-);
for(int i=;i<=L+;i++)total -= ans.m[][i];
printf("%llu\n",total+);
}
}