题解:http://blog.csdn.net/xingyeyongheng/article/details/10005923
这里采用了二分法求等比数列前n项和。
等比数列前n项和也可以用矩乘快速幂来求[a 1] [Sn] = [Sn+1]
[0 1] [a ] [ a ]
#include<cstdio> #include<cstring> #include<vector> #include<queue> #include<iostream> using namespace std; typedef unsigned long long ull; typedef vector<ull> vec; typedef vector<vec> mat; typedef pair<mat,mat> Point2; typedef pair<ull,ull> Point; int N; mat I; mat operator * (const mat &a,const mat &b) { mat c(N,vec(N)); for(int i=0;i<N;++i) for(int j=0;j<N;++j) for(int k=0;k<N;++k) c[i][j]=c[i][j]+a[i][k]*b[k][j]; return c; } mat operator - (const mat &a,const mat &b) { mat c(N,vec(N)); for(int i=0;i<N;++i) for(int j=0;j<N;++j) c[i][j]=a[i][j]-b[i][j]; return c; } mat operator + (const mat &a,const mat &b) { mat c(N,vec(N)); for(int i=0;i<N;++i) for(int j=0;j<N;++j) c[i][j]=a[i][j]+b[i][j]; return c; } Point sum_a_n(ull a,ull n) { if(n==0) return Point(1,1); Point t=sum_a_n(a,n>>1); if(n&1) return Point(t.first*t.first*a,t.second*(t.first*a+1)); else return Point(t.first*t.first,(t.second-t.first)*(t.first*a+1)+t.first); } Point2 sum_A_n(mat a,ull n) { if(n==0) return Point2(I,I); Point2 t=sum_A_n(a,n>>1); if(n&1) return Point2(t.first*t.first*a,t.second*(t.first*a+I)); else return Point2(t.first*t.first,(t.second-t.first)*(t.first*a+I)+t.first); } queue<int>q; int child[40][26],fail[40],size=1; bool word[40]; void Insert(char S[]) { int len=strlen(S); int now=0; for(int i=0;i<len;++i) { if(!child[now][S[i]-'a']) child[now][S[i]-'a']=size++; now=child[now][S[i]-'a']; } word[now]=1; } void build() { fail[0]=-1; q.push(0); while(!q.empty()) { int U=q.front(); q.pop(); for(int i=0;i<26;++i) if(child[U][i]) { int V=fail[U]; while(V!=-1) { if(child[V][i]) { fail[child[U][i]]=child[V][i]; break; } V=fail[V]; } if(V==-1) fail[child[U][i]]=0; if(word[fail[child[U][i]]]) word[child[U][i]]=1; q.push(child[U][i]); } else if(U) child[U][i]=child[fail[U]][i]; } } int n,ma2[40]; ull m; void Init() { memset(child,0,sizeof(child)); memset(fail,0,sizeof(fail)); memset(word,0,sizeof(word)); N=0; size=1; } int main() { //freopen("hdu2243.in","r",stdin); char s[8]; while(cin>>n>>m){ Init(); for(int i=1;i<=n;++i) { scanf("%s",s); Insert(s); } build(); for(int i=0;i<size;++i) if(!word[i]) ma2[i]=N++; I.assign(N,vec(N)); for(int i=0;i<N;++i) I[i][i]=1; mat A(N,vec(N)); for(int i=0;i<size;++i) for(int j=0;j<26;++j) if((!word[i]) && (!word[child[i][j]])) ++A[ma2[i]][ma2[child[i][j]]]; A=sum_A_n(A,m).second-I; ull ans=sum_a_n(26,m).second-1; for(int i=0;i<N;++i) ans=ans-A[0][i]; cout<<ans<<endl; } return 0; }