首页 > 代码库 > poj2778DNA Sequence（AC自动机+矩阵乘法）

poj2778DNA Sequence（AC自动机+矩阵乘法）

2024-07-04 16:47:20   235人阅读

链接

看此题前先看一下matrix67大神写的关于十个矩阵的题目中的一个，如下：

经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
    把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。

再来看此题，与1627是如此的相似，又如此的不同，怒把长度涨到20Y，普通的dp转移无法奏效。

既然已经贴上了大神的讲解，肯定与之有关系，姑且直接拉近距离，我们建立的trie树是有路径可寻的，从root往下走，显然，它是一个有向图，root->a可达 说明他俩之间右边，

抛开病毒不病毒的不讲，长度为n的字符串数不就是从root走n步到达某个j结点的方案数？，那么此题就基本解决了，最后一点是构造A这个矩阵，需要当前结点不为病毒结点。

  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 101
 12 #define LL long long
 13 #define INF 0xfffffff
 14 #define mod 100000
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 const int child_num = 4;
 19 const int _n = 101;
 20 char vir[11];
 21 struct Mat
 22 {
 23     LL mat[N][N];
 24 };
 25 Mat operator * (Mat a,Mat b)
 26 {
 27     Mat c;
 28     memset(c.mat,0,sizeof(c.mat));
 29     int i,j,k;
 30     for(k =0 ; k < _n ; k++)
 31     {
 32         for(i = 0 ; i < _n ;i++)
 33         {
 34             if(a.mat[i][k]==0) continue;//优化
 35             for(j = 0 ;j < _n;j++)
 36             {
 37                 if(b.mat[k][j]==0) continue;//优化
 38                 c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
 39             }
 40         }
 41     }
 42     return c;
 43 }
 44 Mat operator ^(Mat a,int k)
 45 {
 46     Mat c;
 47     int i,j;
 48     for(i =0 ; i < _n ;i++)
 49         for(j = 0; j < _n ;j++)
 50         c.mat[i][j] = (i==j);
 51     for(; k ;k >>= 1)
 52     {
 53         if(k&1) c = c*a;
 54         a = a*a;
 55     }
 56     return c;
 57 }
 58 class AC
 59 {
 60     private:
 61     int ch[N][child_num];
 62     int Q[N];
 63     int fail[N];
 64     int val[N];
 65     int id[128];
 66     int sz;
 67     public:
 68     void init()
 69     {
 70         fail[0] = 0;
 71         id[‘A‘] = 0; id[‘G‘] = 1;
 72         id[‘T‘] = 2; id[‘C‘] = 3;
 73     }
 74     void reset()
 75     {
 76         memset(val,0,sizeof(val));
 77         memset(fail,0,sizeof(fail));
 78         memset(ch[0],0,sizeof(ch[0]));
 79         sz = 1;
 80     }
 81     void insert(char *s,int key)
 82     {
 83         int i,k = strlen(s);
 84         int p = 0;
 85         for(i = 0 ;i < k ;i++)
 86         {
 87             int d = id[s[i]];
 88             if(ch[p][d]==0)
 89             {
 90                 memset(ch[sz],0,sizeof(ch[sz]));
 91                 ch[p][d] = sz++;
 92             }
 93             p = ch[p][d];
 94         }
 95         val[p] = key;
 96     }
 97     void construct()
 98     {
 99         int i,head=0,tail = 0;
100         for(i = 0 ; i < child_num ; i++)
101         {
102             if(ch[0][i])
103             {
104                 Q[tail++] = ch[0][i];
105                 fail[ch[0][i]] = 0;
106             }
107         }
108         while(head!=tail)
109         {
110             int u = Q[head++];
111             val[u]|=val[fail[u]];
112             for(i = 0 ;i < child_num ; i++)
113             {
114                 if(ch[u][i])
115                 {
116                     Q[tail++] = ch[u][i];
117                     fail[ch[u][i]] = ch[fail[u]][i];
118                 }
119                 else ch[u][i] = ch[fail[u]][i];
120             }
121         }
122     }
123     void work(int n)
124     {
125         Mat x;
126         int i,j;
127         memset(x.mat,0,sizeof(x.mat));
128         for(i = 0 ; i < sz ; i++)
129             for(j = 0; j < child_num ; j++)
130             if(!val[ch[i][j]])
131             x.mat[i][ch[i][j]]++;
132         x = x^n;
133         int ans = 0;
134         for(i = 0 ;i < sz ; i++)
135         ans = (ans+x.mat[0][i])%mod;
136         printf("%d\n",ans);
137     }
138 }ac;
139 int main()
140 {
141     int m,n;
142     ac.init();
143     while(cin>>m>>n)
144     {
145         ac.reset();
146         while(m--)
147         {
148             scanf("%s",vir);
149             ac.insert(vir,1);
150         }
151         ac.construct();
152         ac.work(n);
153     }
154     return 0;
155 }
View Code

 


联系
我们