题目链接：hdu_2243_考研路茫茫——单词情结
题意：
让你求包含这些模式串并且长度不小于L的单词种类
题解：
这题是poj2788的升级版，没做过的强烈建议先做那题。
我们用poj2778的方法可以求出不包含这些单词的，然后算出全部种类数，相减就是答案
全部种类数的公式为f[n]=1 + 26^1 + 26^2 +...26^n
AC自动机建出来的矩阵需要在最后添加一列1，这样在矩阵快速幂的时候就能计算出从1~n的幂和
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;i++)
typedef unsigned long long ll;
//-----------------------矩阵-------------------------
const int mat_N=*+;//矩阵阶数
int N;
struct mat{
ll c[mat_N][mat_N];
void init(){mst(c,);}
mat operator*(mat b){
mat M;M.init();
F(i,,N)F(j,,N)F(k,,N)M.c[i][j]=M.c[i][j]+c[i][k]*b.c[k][j];
return M;
}
mat operator^(ll k){
mat ans,M=(*this);ans.init();
F(i,,N)ans.c[i][i]=;
while(k){if(k&)ans=ans*M;k>>=,M=M*M;}
return ans;
}
}A;
//-----------------------AC自动机-----------------------
const int AC_N=**,tyn=;//数量乘串长,类型数
struct AC_automation{
int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot;
inline int getid(char x){return x-'a';}
void nw(){cnt[++tot]=;memset(tr[tot],-,sizeof(tr[tot]));}
void init(){tot=-,fail[]=-,nw();}
void insert(char *s,int x=){
for(int len=strlen(s),i=,w;i<len;x=tr[x][w],i++)
if(tr[x][w=getid(s[i])]==-)nw(),tr[x][w]=tot;
cnt[x]++;//串尾标记
}
void build(int head=,int tail=){
for(Q[++tail]=;head<=tail;){
for(int i=,x=Q[head++],p=-;i<tyn;i++)if(~tr[x][i]){
if(x==)fail[tr[][i]]=;
else for(p=fail[x],fail[tr[x][i]]=;~p;p=fail[p])
if(~tr[p][i]){fail[tr[x][i]]=tr[p][i];break;}
if(cnt[fail[tr[x][i]]])cnt[tr[x][i]]=;
Q[++tail]=tr[x][i];
}else if(x==)tr[x][i]=;
else tr[x][i]=tr[fail[x]][i];
}
}
}AC; void build_mat()
{
A.init();
F(i,,AC.tot)F(j,,)if(!AC.cnt[i]&&!AC.cnt[AC.tr[i][j]])A.c[i][AC.tr[i][j]]++;
N=AC.tot+;
F(i,,N)A.c[i][N]=;//矩阵添加一列1，能将矩阵从1~n的幂和算出来
} ll q_pow(ll k)
{
unsigned long long ans=,tp=;
while(k){if(k&)ans*=tp;k>>=,tp*=tp;}
return ans;
} ll f_ck(ll k)//计算26的从1~k的幂和
{
if(k==)return ;
ll t=;
if(k&)t=q_pow(k);
return (+q_pow(k>>))*f_ck(k>>)+t;
} int main()
{
ll n,m,ans,tp;char buf[];
while(~scanf("%llu%llu",&n,&m))
{
AC.init();
F(i,,n)scanf("%s",buf),AC.insert(buf);
AC.build(),build_mat(),A=A^m,ans=;
F(i,,N)ans+=A.c[][i];
tp=f_ck(m);
printf("%llu\n",tp-ans+);
}
return ;
}