题目链接
考研路茫茫――单词情结 HDU - 2243
题目
背单词，始终是复习英语的重要环节。在荒废了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实在是数不出来了，现在就请你帮帮他。
Input
本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0
分析
总字符串个数为26+26^2+26^3+…+26^n.
包含词根的字符串个数为A+A^2+A^3+…A^n所得到的矩阵的第一行的值的和。A为根据AC自动机确定的状态转移图对应的矩阵。
这题就是POJ2778的变形。
DNA Sequence POJ - 2778
（求不包含特定字符串的长度为N的字符串总数）
变形的部分就是POJ3233
(给定矩阵A，求A+A^2+A^3+…+A^n的结果）
大致的解题思路就是
A+A^2+A^3+…+A^6=A+A^2+A^3+A^3(A+A^2+A^3).
递归求（A+A^2+A^3)并注意讨论下n的奇偶性即可。
AC代码
//187ms 13.1MB
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
typedef unsigned long long ll;
using namespace std;
const int maxn=50; //单词长度*单词数,结点总数
const int maxc=26; //树分支数//在trie上添加后缀结点
//后缀结点：x的后缀结点为非x结点y，
//y的路径字符串为x的路径字符串的最长后缀且y的路径字符串是单词
struct ac_au
{int child[maxn][maxc];//trieint fail[maxn];//后缀结点int sta[maxn];//是否为含词根字符串的尾结点int cnt;//结点的个数int root; //根结点int newnode(){for(int i=0;i<maxc;i++)child[cnt][i]=-1;sta[cnt++]=0;return cnt-1;}void init(){cnt=0;root=newnode();}int getid(char ch){return ch-'a';}void insert(char *s)//trie构建{int len=strlen(s),p=0;for(int i=0;i<len;i++){int c=getid(s[i]);//第c个儿子int &num=child[p][c];if(num==-1)num=newnode();p=num;}sta[p]=1;//是词根字符串的尾结点}void build()//后缀结点的添加{int p=0;queue<int> que;for(int i=0;i<maxc;i++){int &num=child[p][i];if(num==-1)num=p;//为下文铺垫，和树意义无关else{fail[num]=p;//有点多余，初始化都是0，理解算法过程有用que.push(num);}}while(!que.empty()){p=que.front();que.pop();int x=fail[p];//p的后缀结点为x//后缀结点的确定是通过bfs，由浅层到深层，故每一个在队列中的结点都确定了后缀结点if(sta[x]) sta[p]=1;//其后缀结点为含病毒字符串尾结点，//说明p也是含词根字符串尾结点，可能不是词根，但一定包含词根for(int i=0;i<maxc;i++){int &num=child[p][i];//引用，改变num就改变child[p][i]if(num==-1)num=child[fail[p]][i];else{fail[num]=child[fail[p]][i];que.push(num);}}}}}ac;
struct matrix
{ll m[50][50];//相当于模2^64matrix(){for(int i=0;i<ac.cnt;i++)for(int j=0;j<ac.cnt;j++)m[i][j]=0;}
};
matrix mul(matrix A,matrix B)//矩阵乘法
{matrix C;for(int i=0; i<ac.cnt; i++)for(int j=0; j<ac.cnt; j++){C.m[i][j]=0;for(int k=0; k<ac.cnt; k++){ll tmp=A.m[i][k]*B.m[k][j];C.m[i][j]=(C.m[i][j]+tmp);}}return C;
}
matrix pow(matrix A,ll k)//矩阵快速幂
{matrix ans=A;matrix x=A;k--;while(k){if(k&1)ans=mul(ans,x);k>>=1;x=mul(x,x);}return ans;
}
matrix getMatrix() //从AC自动机得到状态转移图对应的矩阵
{matrix A=matrix();for(int i=0; i<ac.cnt; i++)for(int j=0; j<maxc; j++){//如果从u结点走到v结点不会使得字符串变成含词根字符串，则合法，可以连边int u=i;int v=ac.child[u][j];if(!ac.sta[v])A.m[u][v]++;}return A;
}
matrix add(matrix A,matrix B)//矩阵加法
{matrix ans;for(int i=0;i<ac.cnt;i++)for(int j=0;j<ac.cnt;j++)ans.m[i][j]=A.m[i][j]+B.m[i][j];return ans;
}
matrix sum(matrix A,int k)//求A+A^2+A^3+...+A^k
{matrix ans,x,y;if(k==1) return A;x=sum(A,k>>1);if(k&1)//另一种递归形式：将奇数看作偶数+A^k会超内存{y=pow(A,k/2+1);ans=add(x,y);ans=add(ans,mul(x,y));}else{y=pow(A,k>>1);ans=add(x,mul(x,y));}return ans;
}
ll _pow(int k)//快速幂
{ll ans=1,x=26;while(k){if(k&1) ans=ans*x;k>>=1;x=x*x;}return ans;
}ll all(ll k) //求26+26^2+26^3+...+26^k
{if(k==1)return 26;ll ans,x,y;x=all(k>>1);if(k&1){y=_pow(k/2+1);ans=x+y+x*y;}else{y=_pow(k/2);ans=x+x*y;}return ans;
}
char s[105];
int main()
{int n,k;while(~scanf("%d%d",&n,&k)){ac.init();for(int i=1; i<=n; i++){scanf("%s",s);ac.insert(s);}ac.build();matrix A=getMatrix();matrix ans=sum(A,k);ll res=0;ll tmp=all(k);for(int i=0;i<ac.cnt;i++)res=(res+ans.m[0][i]);res=tmp-res;printf("%I64u\n",res);//unsigned long long的输出格式为%I64u}return 0;
}