HDU

题解：这题基本跟poj2778一样，我们可以把所有的情况的个数计算出来=26^1+26^2+26^3+......+26^m。这个我们可以用矩阵快速幂，构造一个矩阵{26,0;26,1;}，他的次幂只后a[1][0]位置的值就是所有情况的个位数，然后在减去不含任何给定词根的个数这里就是poj2778，也是构造矩阵，通过离散数学一个矩阵m的K次幂之后m[i][j]表示从i到j走K布有m[i][j]种方法，这样的话我们就可建立ac自动机，构建初始矩阵A,然后在求AA=A+A^2+A^3+....A^m（这个如何求可以先看下这个）, 然后AA第一行的和就是不满足情况的个数。

做这题之前建议先做poj2778 poj3233

ac代码有点长,但我用的是模板以后可以照搬着用

  1 #include<bits/stdc++.h>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<iomanip>
  5 #include<iostream>
  6 #include<string>
  7 #include<cstring>
  8 #include<algorithm>
  9 #define ll long long
 10 using namespace std;
 11 typedef unsigned long long ull;
 12 const ull mod=1ll<<64;
 13 const int maxn=1e5+10;
 14 const int N=6*5+10;
 15 int n,m;
 16 struct mat
 17 {
 18     int n, m;
 19     ull a[N*2][N*2];
 20     mat() {}
 21     void init(int _n, int _m)
 22     {
 23         n = _n;
 24         m = _m;
 25         for(int i = 0; i < n; i++)
 26         {
 27             for(int j = 0; j < m; j++) a[i][j] = 0;
 28         }
 29     }
 30     mat operator + (const mat &B)const
 31     {
 32         mat C;
 33         C.init(n,m);
 34         for(int i=0; i<n; i++)
 35             for(int j=0; j<m; j++)
 36                 C.a[i][j]=(a[i][j]+B.a[i][j]);
 37         return C;
 38     }
 39     mat operator*(const mat &P)const
 40     {
 41         mat ret;
 42         ret.init(n,m);
 43         for(int i = 0; i < n; i++)
 44         {
 45             for(int k = 0; k < m; k++)
 46             {
 47                 if(a[i][k])
 48                 {
 49                     for(int j = 0; j < P.m; j++)
 50                     {
 51                         ret.a[i][j] = (a[i][k] * P.a[k][j] + ret.a[i][j]) ;
 52                     }
 53                 }
 54             }
 55         }
 56         return ret;
 57     }
 58     mat operator^(const ll &P)const
 59     {
 60         ll num = P;
 61         mat ret, tmp = *this;
 62         ret.init(n,m);
 63         for(int i = 0; i < n; i++) ret.a[i][i] = 1;
 64         while(num)
 65         {
 66             if(num & 1) ret = ret * tmp;
 67             tmp = tmp * tmp;
 68             num >>= 1;
 69         }
 70         return ret;
 71     }
 72     void view()
 73     {
 74         for(int i=0;i<n;i++)
 75         {
 76             for(int j=0;j<m;j++)
 77             {
 78                 printf("%llu ",a[i][j]);
 79             }printf("
");
 80         }
 81     }
 82 }ap,ad;
 83 struct ac_auto
 84 {
 85     int nxt[N][26],ed[N],fail[N],cn,rt;
 86     void init(){
 87         cn=0;
 88         rt=new_node();
 89     }
 90     int new_node()
 91     {
 92         memset(nxt[cn],-1,sizeof(nxt[cn]));
 93         ed[cn]=0;fail[cn]=-1;
 94         return cn++;
 95     }
 96     void insert(char *s)
 97     {
 98         int len=strlen(s);
 99         int p=rt;
100         for(int i=0;i<len;i++)
101         {
102             int x=s[i]-'a';
103             if(nxt[p][x]==-1)nxt[p][x]=new_node();
104             p=nxt[p][x];
105         }
106         ed[p]++;
107     }
108         void construct()
109             {
110                 queue<int> Q;
111                fail[0] = 0;
112                 for (int i = 0; i < 26; i++)
113                 {
114                     if (-1 != nxt[0][i])
115                     {
116                         fail[nxt[0][i]] = 0;
117                         Q.push(nxt[0][i]);
118                     }
119                     else
120                     {
121                         nxt[0][i] = 0;    //这个不能丢
122                     }
123                 }
124                 while ( !Q.empty() )
125                 {
126                     int u = Q.front();
127                     Q.pop();
128                     if (ed[fail[u]])
129                         ed[u] = true;         //这个很重要，当u的后缀是病毒，u也不能出现
130                     for (int i = 0; i < 26; i++)
131                     {
132                         int &v = nxt[u][i];
133                         if ( -1 != v )
134                         {
135                             Q.push(v);
136                             fail[v] = nxt[fail[u]][i];
137                         }
138                         else
139                         {
140                             v = nxt[fail[u]][i];
141                         }
142                     }
143                 }
144             }
145 
146     void get_mat()
147     {
148         ap.init(cn,cn+cn);
149         for(int i=0;i<cn;i++)
150         {
151             for(int j=0;j<26;j++)
152             {
153                 if(!ed[i]&&!ed[nxt[i][j]])
154                 {
155                     ap.a[i][nxt[i][j]]++;
156                 }
157             }
158         }
159         for(int i=0;i<cn;i++)
160         {
161             ap.a[i][i+cn]=1;
162         }
163     }
164     void view(int x)
165     {
166         cout<<x<<" "<<ed[x]<<" "<<fail[x]<<" "<<nxt[x][0]<<" "<<nxt[x][1]<<" "<<nxt[x][2]<<" "<<nxt[x][3]<<endl;
167         for(int i=0;i<4;i++)
168         {
169             if(nxt[x][i]!=-1)view(nxt[x][i]);
170         }
171     }
172 }ac;
173 int main()
174 {
175     char op[15];
176    // cout<<(((1ull<<63)-1)<<1)+1<<endl;
177   //  cout<<1ull-2<<endl;
178     while(~scanf("%d %d",&n,&m))
179     {
180         ull an1;
181         mat t2;
182         t2.init(2,2);
183         t2.a[0][0]=t2.a[1][0]=26;
184         t2.a[1][1]=1;
185         t2=t2^m;
186         an1=t2.a[1][0];
187         ac.init();
188         for(int i=1;i<=n;i++)
189         {
190             scanf("%s",op);
191             ac.insert(op);
192         }
193         ac.construct();
194         ac.get_mat();
195         ad.init(ac.cn*2,ac.cn*2);
196         for(int i=0;i<ac.cn;i++)
197         {
198             ad.a[i+ac.cn][i+ac.cn]=1;
199             for(int j=0;j<ac.cn;j++)
200             {
201                 ad.a[i+ac.cn][j]=ad.a[i][j]=ap.a[i][j];
202             }
203         }
204         ap=ap*(ad^(m-1));
205         for(int i=0;i<ac.cn;i++)
206         {
207             an1-=ap.a[0][i];
208         }
209         printf("%llu
",an1);
210     }
211     return 0;
212 }