跟2778差不多，解决了那道题这道也不成问题如果做过基本的矩阵问题。
数比较大，需要用unsigned longlong 就不需要mod了 溢出就相当于取余
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 30 12 #define LL unsigned __int64 13 #define INF 0xfffffff 14 #pragma comment(linker, "/STACK:1024000000,1024000000") 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 const int mn = 30; 19 const int child_num = 26; 20 struct Mat 21 { 22 LL mat[N][N]; 23 }; 24 Mat operator *(Mat a,Mat b) 25 { 26 Mat c; 27 memset(c.mat,0,sizeof(c.mat)); 28 int i,j,k; 29 for(k =0 ; k < mn ; k++) 30 { 31 for(i = 0 ; i < mn ;i++) 32 { 33 if(a.mat[i][k]==0) continue;//优化 34 for(j = 0 ;j < mn ;j++) 35 { 36 if(b.mat[k][j]==0) continue;//优化 37 c.mat[i][j] = c.mat[i][j]+(a.mat[i][k]*b.mat[k][j]); 38 } 39 } 40 } 41 return c; 42 } 43 Mat operator + (Mat a,Mat b) 44 { 45 Mat c; 46 memset(c.mat,0,sizeof(c.mat)); 47 int i,j; 48 for(i = 0 ; i < mn ;i++) 49 for(j = 0 ;j < mn ;j++) 50 c.mat[i][j] = a.mat[i][j]+b.mat[i][j]; 51 return c; 52 } 53 Mat operator ^(Mat a,int k) 54 { 55 Mat c; 56 int i,j; 57 for(i =0 ; i < mn ;i++) 58 for(j = 0; j < mn ;j++) 59 c.mat[i][j] = (i==j); 60 for(; k ;k >>= 1) 61 { 62 if(k&1) c = c*a; 63 a = a*a; 64 } 65 return c; 66 } 67 Mat cal(Mat x,int k) 68 { 69 if(k==1) return x; 70 Mat c,cc; 71 c = cal(x,k/2); 72 cc = x^(k/2); 73 c = c+cc*c; 74 if(k&1) 75 c = c+(x^k); 76 return c; 77 } 78 LL ex_mod(int a,int k) 79 { 80 if(k==1) return a; 81 LL t = ex_mod(a,k/2); 82 t = t*t; 83 if(k&1) 84 t = t*a; 85 return t; 86 } 87 LL solve(int a,int k) 88 { 89 if(k==1) return a; 90 LL t = solve(a,k/2); 91 t = t + ex_mod(a,k/2)*t; 92 if(k&1) t = t+ex_mod(a,k); 93 return t; 94 } 95 class AC 96 { 97 private: 98 int ch[N][child_num]; 99 int Q[N]; 100 int fail[N]; 101 int val[N]; 102 int sz; 103 int id[228]; 104 public : 105 void init() 106 { 107 fail[0] = 0; 108 for(int i = 0 ; i < child_num ; i++) 109 id[i+'a'] = i; 110 } 111 void reset() 112 { 113 memset(val,0,sizeof(val)); 114 memset(ch[0],0,sizeof(ch[0])); 115 memset(fail,0,sizeof(fail)); 116 sz = 1; 117 } 118 void insert(char *a,int key) 119 { 120 int p = 0; 121 for(; *a ;a++) 122 { 123 int d = id[*a]; 124 if(ch[p][d]==0) 125 { 126 memset(ch[sz],0,sizeof(ch[sz])); 127 ch[p][d] = sz++; 128 } 129 p = ch[p][d]; 130 } 131 val[p] = key; 132 } 133 void construct() 134 { 135 int i; 136 int head =0, tail=0; 137 for(i = 0;i < child_num ;i++) 138 { 139 if(ch[0][i]) 140 { 141 fail[ch[0][i]] = 0; 142 Q[tail++] = ch[0][i]; 143 } 144 } 145 while(head!=tail) 146 { 147 int u = Q[head++]; 148 val[u]|=val[fail[u]]; 149 for(i= 0; i < child_num ; i++) 150 { 151 if(ch[u][i]) 152 { 153 fail[ch[u][i]] = ch[fail[u]][i]; 154 Q[tail++] = ch[u][i]; 155 } 156 else ch[u][i] = ch[fail[u]][i]; 157 } 158 } 159 } 160 void work(int n) 161 { 162 int i; 163 Mat x; 164 memset(x.mat,0,sizeof(x.mat)); 165 for(i = 0 ; i < sz; i++) 166 { 167 for(int j = 0; j < child_num ; j++) 168 if(val[ch[i][j]]==0) 169 x.mat[i][ch[i][j]]++; 170 } 171 x = cal(x,n); 172 LL ans = 0; 173 for(i = 0 ; i < sz ; i++) 174 ans = ans+x.mat[0][i]; 175 ans = solve(26,n)-ans; 176 cout<<ans<<endl; 177 } 178 }ac; 179 char vir[20]; 180 int main() 181 { 182 int n,l,i; 183 ac.init(); 184 while(scanf("%d%d",&n,&l)!=EOF) 185 { 186 ac.reset(); 187 for(i = 1; i <= n; i++) 188 { 189 scanf("%s",vir); 190 ac.insert(vir,1); 191 } 192 ac.construct(); 193 ac.work(l); 194 } 195 return 0; 196 }