POJ - 2778 DNA Sequence（AC自动机+矩阵快速幂）

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<string.h>
  5 #define ll long long
  6 using namespace std;
  7 
  8 const ll mod=1e5;
  9 const ll maxn = 111;
 10 const ll MX = 111;
 11 ll ans=0;
 12 ll d['Z'+1];
 13 
 14 struct tire{
 15     ll nxt[maxn][4],fail[maxn],end[maxn],tot,root,vis[maxn];
 16     ll newNode(){
 17         for(ll i=0;i<4;i++) nxt[tot][i] = -1;
 18         end[tot++] = 0;
 19         return tot-1;
 20     }
 21     void Init(){
 22         tot = 0;
 23         root = newNode();
 24         ans=0;
 25     }
 26     void Insert(char *buf){
 27         ll len = strlen(buf),i,u = root;
 28         for(i=0;i<len;i++){
 29             ll x = d[buf[i]];
 30             if(nxt[u][x]==-1) nxt[u][x] = newNode();
 31             u = nxt[u][x];
 32         }
 33         end[u] = 1;
 34     }
 35     void build(){
 36         queue <ll> q;
 37         fail[root] = root;
 38         for(ll i=0;i<4;i++){
 39             if(nxt[root][i]==-1) nxt[root][i] = root;
 40             else{
 41                 fail[nxt[root][i]] = root;
 42                 q.push(nxt[root][i]);
 43             }
 44             end[nxt[root][i]]|=end[fail[nxt[root][i]]];
 45         }
 46         while(!q.empty()){
 47             ll now = q.front();
 48             q.pop();
 49             for(ll i=0;i<4;i++){
 50                 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i];
 51                 else{
 52                     fail[nxt[now][i]] = nxt[fail[now]][i];
 53                     q.push(nxt[now][i]);
 54                 }
 55                 end[nxt[now][i]]|=end[fail[nxt[now][i]]];
 56             }
 57         }
 58     }
 59 }ac;
 60 
 61 struct Mat{
 62     ll mat[maxn][maxn];
 63 };
 64 
 65 Mat operator * (Mat a, Mat b) {
 66     Mat c;
 67     ll i, j, k;
 68     memset(c.mat, 0, sizeof(c.mat));
 69     for (i = 0; i <= ac.tot; i++)
 70         for (j = 0; j <= ac.tot; j++)
 71             for (k = 0; k <= ac.tot; k++) {
 72                 c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
 73                 c.mat[i][j] %= mod;
 74             }
 75     return c;
 76 }
 77 
 78 Mat operator ^ (Mat a, ll b) {
 79     Mat c;
 80     ll i, j;
 81     for (i = 0; i <= ac.tot; i++)
 82         for (j = 0; j <= ac.tot; j++)
 83             c.mat[i][j] = (i == j);
 84     while(b != 0) {
 85         if (b & 1 != 0) c = c * a;
 86             a = a * a;
 87             b /= 2;
 88     }
 89     return c;
 90 }
 91 
 92 char s1[MX];
 93 
 94 int main()
 95 {
 96     ios::sync_with_stdio(false);
 97     cin.tie(0);
 98     cout.tie(0);
 99     ll t,n,m;
100     cin>>n>>m;
101     d['A']=0,d['C']=1,d['T']=2,d['G']=3;
102     ac.Init();
103     for(ll i=0;i<n;i++) cin>>s1,ac.Insert(s1);
104     ac.build();
105     Mat a,b;
106     for(ll i=0;i<=ac.tot;i++){
107         if(ac.end[i]) continue;
108         for(ll j=0;j<4;j++){
109             if(ac.end[ac.nxt[i][j]]) continue;
110             a.mat[i][ac.nxt[i][j]]++;
111         }
112     }
113     b=a^m;
114     for(ll i=0;i<=ac.tot;i++){
115         ans+=b.mat[0][i];
116         ans%=mod;
117     }
118     cout<<ans<<endl;
119     return 0;
120 }