根据AC自动机构造矩阵，然后对到矩阵模板里跑一跑就好了。
设所有情况的总数为 sum，不合法数为 non，则答案anw = sum – non。
首先sum = sigma(26^i) (1 <= i <= n)，这个矩阵或者二分皆可搞。
然后non 为 所有不含词根的情况。
对于所有的AC自动机上的节点 i 枚举下一个可能的字符，即‘a’ – ‘z’，然后根据自动机的规则肯定会转移到某个节点 j ,如果 j 及 j 通过fail指针回指到root的路径上均无标记，
那么mat[i][j] ++，，表示i->j有多了一种方式或者一条路。
然后学过《离散数学》都会知道A[][] = mat[][]^K表示A[i][j]有多少种长度为K的走法。
那么non = sigma(mat[][]^i) (1 <= i <= n)。
然后anw = sum – non。
#include <iostream>#include<time.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<string>#include<map>#include<vector>#include <algorithm>#include <queue>#define LL long long#define ULL unsigned long longusing namespace std;const int MAXS = 26,MAXN = 35;const int MATN = 70;struct MAT{int row,col;ULL mat[MATN][MATN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1;i <= row; ++i)for(int j = 1;j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,LL MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(k = 1;k <= this->col; ++k)for(i = 1;i <= tmp.row; ++i)for(j = 1;j <= tmp.col; ++j)tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j]);return tmp;}MAT Quick(LL n,LL MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1;i <= row; ++i){for(j = 1;j <= col; ++j)printf("%3lld ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};struct Trie{int next[MAXS];int fail;int flag;} st[MAXN];queue<int> q;struct ACautomaton{int Top,root;int Creat(){memset(st[Top].next,-1,sizeof(st[Top].next));st[Top].flag = 0;st[Top].fail = -1;return Top++;}void Init(){Top = 0;root = Creat();}inline int CalIndex(char c){return c-'a';}void Insert(char *s){int i = 0,tr = root,tmp;while(s[i] != '\0'){tmp = CalIndex(s[i]);if(st[tr].next[tmp] == -1)st[tr].next[tmp] = Creat();tr = st[tr].next[tmp],++i;}st[tr].flag = 1;}void GetFail(){st[root].fail = -1;q.push(root);int f,t;while(q.empty() == false){f = q.front();q.pop();for(int i = 0; i < MAXS; ++i){if(st[f].next[i] != -1){t = st[f].fail;while(t != -1 && st[t].next[i] == -1)t = st[t].fail;if(t == -1)st[st[f].next[i]].fail = root;elsest[st[f].next[i]].fail = st[t].next[i];q.push(st[f].next[i]);}}}}int Match(char *s){int i ,tr = root,tmp;int ans = 0;for(i = 0; s[i] != '\0'; ++i){if(s[i] < 'A' || 'Z' < s[i]){tr = root;continue;}tmp = CalIndex(s[i]);while(tr != -1 && st[tr].next[tmp] == -1 )tr = st[tr].fail;if(tr == -1){tr = root;continue;}tr = st[tr].next[tmp];tmp = tr;while(tmp != root && st[tmp].flag != -1){if(st[tmp].flag)ans++,st[tmp].flag = -1;}}return ans;}void GetMat(MAT &A){int i,j,tr;for(i = 0;i < Top; ++i){for(j = 0;j <MAXS; ++j){tr = i;while(tr != -1){if(st[tr].next[j] != -1 && st[st[tr].next[j]].flag != 0)break;tr = st[tr].fail;}if(tr != -1)continue;tr = i;while(tr != -1){if(st[tr].next[j] != -1)break;tr = st[tr].fail;}if(tr == -1)A.mat[i+1][1] ++;elseA.mat[i+1][st[tr].next[j]+1] ++;}}}};ULL CAL(ULL x,ULL n){if(n == 0)return 1;if(n == 1)return x;ULL tmp = CAL(x,n/2);return tmp*tmp*CAL(x,n&1);}int main(){int n,m;ACautomaton AC;char s[15];MAT A,B,C;while(scanf("%d %d",&n,&m) != EOF){AC.Init();while(n–){scanf("%s",s);AC.Insert(s);}AC.GetFail();A.Init(AC.Top*2,AC.Top*2,0);B.Init(2*AC.Top,AC.Top,0);AC.GetMat(A);for(int i = 1;i <= AC.Top; ++i)A.mat[AC.Top+i][i] = A.mat[AC.Top+i][AC.Top+i] = 1;for(int i = 1;i <= AC.Top; ++i)for(int j = 1;j <= AC.Top; ++j)B.mat[i][j] = A.mat[i][j];A = A.Quick(m,1);A = A.Multi(B,1);B.Init(2,1,0);B.mat[1][1] = 26;C.Init(2,2,0);C.mat[1][1] = 26;C.mat[1][2] = 0;C.mat[2][1] = 1;C.mat[2][2] = 1;C = C.Quick(m,1).Multi(B,1);ULL sum = C.mat[2][1];for(int i = 1;i <= AC.Top; ++i)sum = sum – A.mat[AC.Top+1][i];cout<<sum<<endl;}return 0;}
旅行要学会随遇而安，淡然一点，走走停停，
