考研路茫茫——单词情结
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2243
64-bit integer IO format: %I64d Java class name: Main
背单词，始终是复习英语的重要环节。在荒废了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。两个词根中间用一个空格分隔开。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。
Output
对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
Sample Input
2 3
aa ab
1 2
a
Sample Output
104
52 解题：Trie图+矩阵快速幂
可以将$A+A^2+A^2+\cdots+A^n$转而求\[\begin{bmatrix} A & A \\ 0 & 1 \end{bmatrix}^n\]
然后矩阵快速幂加速
#include <stdio.h>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
using ULL = unsigned long long;
const int maxn = ;
struct Matrix{
ULL m[maxn][maxn],n;
void init(int sz,bool one){
memset(m,,sizeof m);
n = sz;
if(one) for(int i = ; i < n; ++i) m[i][i] = ;
}
Matrix(int sz,bool one = false){
init(sz,one);
}
Matrix operator*(const Matrix &rhs){
Matrix ret(n);
for(int k = ; k < n; ++k){
for(int i = ; i < n; ++i)
for(int j = ; j < n; ++j)
ret.m[i][j] += m[i][k]*rhs.m[k][j];
}
return ret;
}
Matrix operator^(int index){
Matrix ret(n,true);
while(index){
if(index&) ret = ret*(*this);
index >>= ;
*this = (*this)*(*this);
}
return ret;
}
void out(){
for(int i = ; i < n; ++i){
for(int j = ; j < n; ++j)
cout<<m[i][j]<<" ";
cout<<endl;
}
}
};
struct Trie{
int ch[maxn*maxn][],fail[maxn*maxn],cnt[maxn*maxn],tot;
void init(){
tot = ;
newnode();
}
int newnode(){
memset(ch[tot],,sizeof ch[tot]);
fail[tot] = cnt[tot] = ;
return tot++;
}
void insert(char *str,int root = ){
for(int i = ; str[i]; ++i){
int &x = ch[root][str[i]-'a'];
if(!x) x = newnode();
root = x;
}
++cnt[root];
}
void build(int root = ){
int q[maxn*maxn],hd = ,tl = ;
for(int i = ; i < ; ++i)
if(ch[root][i]) q[tl++] = ch[root][i];
while(hd < tl){
root = q[hd++];
cnt[root] += cnt[fail[root]];
for(int i = ; i < ; ++i){
int &x = ch[root][i],y = ch[fail[root]][i];
if(x){
fail[x] = y;
q[tl++] = x;
}else x = y;
}
}
}
ULL solve(int m){
Matrix a();
a.m[][] = a.m[][] = ;
a.m[][] = ;
Matrix b = a^m;
ULL ret = b.m[][];
a.init(tot*,false);
for(int i = ; i < tot; ++i){
if(cnt[i]) continue;
for(int j = ; j < ; ++j){
int x = ch[i][j];
if(cnt[x]) continue;
++a.m[i][x];
a.m[i][x + tot] = a.m[i][x];
}
}
for(int i = tot; i < *tot; ++i) a.m[i][i] = ;
b = a^m;
for(int i = tot; i < *tot; ++i)
ret -= b.m[][i];
return ret;
}
}ac;
int main(){
int n,m;
char str[];
while(~scanf("%d%d",&n,&m)){
ac.init();
for(int i = ; i < n; ++i){
scanf("%s",str);
ac.insert(str);
}
ac.build();
printf("%I64u\n",ac.solve(m));
}
return ;
}