POJ - 2778 ~ HDU - 2243 AC自动机+矩阵快速幂-白红宇

POJ - 2778 ~ HDU - 2243 AC自动机+矩阵快速幂

阅读量：5030 次

发布时间：2019-06-12

本文共 6594 字，大约阅读时间需要 21 分钟。

这两题属于AC自动机的第二种套路通过矩阵快速幂求方案数。

题意：给m个病毒字符串，问长度为n的DNA片段有多少种没有包含病毒串的。

根据AC自动机的tire图，我们可以获得一个可达矩阵。

关于这题的tire图详解可以，往下面翻，这个博主的图对于tire图讲的非常详细。

知道了什么是tire图，理解了tire图后，后面的AC自动机的题目才能写。

AC自动机的灵魂应该就是tire图

然后问题就变成了，得到了一个可达矩阵后，如何求方案数呢？

这个n = 2000000000 这咋办呢？

给定一个有向图，问从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即可。

是不是就是一个裸的矩阵快速幂了。

通过AC自动机得到可达矩阵，然后通过矩阵快速幂求方案数。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 14 #define pi acos(-1.0) 15 #define eps 1e-9 16 #define fi first 17 #define se second 18 #define rtl rt<<1 19 #define rtr rt<<1|1 20 #define bug printf("******\n") 21 #define mem(a, b) memset(a,b,sizeof(a)) 22 #define name2str(x) #x 23 #define fuck(x) cout<<#x" = "<
                  
                   <
                   
                    >= 1; 74 } 75 return ret; 76 } 77 78 struct Aho_Corasick { 79 int next[50010][4], fail[50010], End[50010]; 80 int root, cnt; 81 82 int newnode() { 83 for (int i = 0; i < 4; i++) next[cnt][i] = -1; 84 End[cnt++] = 0; 85 return cnt - 1; 86 } 87 88 void init() { 89 cnt = 0; 90 root = newnode(); 91 } 92 93 int get_num(char ch) { 94 if (ch == 'A') return 0; 95 if (ch == 'T') return 1; 96 if (ch == 'C') return 2; 97 if (ch == 'G') return 3; 98 } 99 100 void insert(char buf[]) {101 int len = strlen(buf);102 int now = root;103 for (int i = 0; i < len; i++) {104 if (next[now][get_num(buf[i])] == -1) next[now][get_num(buf[i])] = newnode();105 now = next[now][get_num(buf[i])];106 }107 End[now]++;108 }109 110 void build() {111 queue
                    
                      Q;112 fail[root] = root;113 for (int i = 0; i < 4; i++)114 if (next[root][i] == -1) next[root][i] = root;115 else {116 fail[next[root][i]] = root;117 Q.push(next[root][i]);118 }119 while (!Q.empty()) {120 int now = Q.front();121 Q.pop();122 if (End[fail[now]]) End[now] = 1;123 for (int i = 0; i < 4; i++)124 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];125 else {126 fail[next[now][i]] = next[fail[now]][i];127 Q.push(next[now][i]);128 }129 }130 }131 132 Matrix get_Matrix() {133 Matrix ret = Matrix(cnt);134 for (int i = 0; i < cnt; ++i) {135 for (int j = 0; j < 4; ++j) {136 if (End[next[i][j]]) continue;137 ret.mat[i][next[i][j]]++;138 }139 }140 return ret;141 }142 143 int query(char buf[]) {144 int len = strlen(buf);145 int now = root;146 int res = 0;147 for (int i = 0; i < len; i++) {148 now = next[now][buf[i] - 'a'];149 int temp = now;150 while (temp != root) {151 res += End[temp];152 End[temp] = 0;153 temp = fail[temp];154 }155 }156 return res;157 }158 159 void debug() {160 for (int i = 0; i < cnt; i++) {161 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);162 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);163 printf("]\n");164 }165 }166 } ac;167 168 int n, m;169 char str[maxn];170 171 int main() {172 // FIN;173 sff(m, n);174 ac.init();175 for (int i = 0; i < m; ++i) {176 scanf("%s", str);177 ac.insert(str);178 }179 ac.build();180 Matrix mat = ac.get_Matrix();181 mat = pow_M(mat, n);182 LL ans = 0;183 for (int i = 0; i < mat.n; ++i) {184 ans = (ans + mat.mat[0][i]) % mod;185 }186 printf("%lld\n", ans);187 return 0;188 }

View Code

考研路茫茫――单词情结 HDU - 2243

这题和上题题意类似，做法一样。

上题是说长度为n的不包含m个模式串的方案数，这题求的是长度为1~n不包括m个模式串的方案数。

这题就在矩阵上面加上一列全为1的列，这个可以1保存了前面的方案书之和。

如果不理解的话，建议通过手算一下矩阵，去看看这个新加的一列有什么用。

这题是对2^64取模，所以直接用unsigned long long 自动溢出取模即可。

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     >= 1; 75 } 76 return ret; 77 } 78 79 struct Aho_Corasick { 80 int next[10010][26], fail[10010], End[10010]; 81 int root, cnt; 82 83 int newnode() { 84 for (int i = 0; i < 26; i++) next[cnt][i] = -1; 85 End[cnt++] = 0; 86 return cnt - 1; 87 } 88 89 void init() { 90 cnt = 0; 91 root = newnode(); 92 } 93 94 void insert(char buf[]) { 95 int len = strlen(buf); 96 int now = root; 97 for (int i = 0; i < len; i++) { 98 if (next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode(); 99 now = next[now][buf[i] - 'a'];100 }101 End[now]++;102 }103 104 void build() {105 queue
                     
                       Q;106 fail[root] = root;107 for (int i = 0; i < 26; i++)108 if (next[root][i] == -1) next[root][i] = root;109 else {110 fail[next[root][i]] = root;111 Q.push(next[root][i]);112 }113 while (!Q.empty()) {114 int now = Q.front();115 Q.pop();116 if (End[fail[now]]) End[now] = 1;117 for (int i = 0; i < 26; i++)118 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];119 else {120 fail[next[now][i]] = next[fail[now]][i];121 Q.push(next[now][i]);122 }123 }124 }125 126 Matrix get_Matrix() {127 Matrix ret = Matrix(cnt+1);128 for (int i = 0; i < cnt; ++i) {129 for (int j = 0; j < 26; ++j) {130 if (!End[next[i][j]]) ret.mat[i][next[i][j]]++;131 }132 }133 for (int i = 0; i <= cnt; ++i) ret.mat[i][cnt] = 1;134 return ret;135 }136 137 int query(char buf[]) {138 int len = strlen(buf);139 int now = root;140 int res = 0;141 for (int i = 0; i < len; i++) {142 now = next[now][buf[i]];143 int temp = now;144 while (temp != root) {145 res += End[temp];146 End[temp] = 0;147 temp = fail[temp];148 }149 }150 return res;151 }152 153 void debug() {154 for (int i = 0; i < cnt; i++) {155 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);156 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);157 printf("]\n");158 }159 }160 } ac;161 162 163 164 char buf[1000010];165 LL n, m;166 167 int main() {168 // FIN;169 while (~scanf("%lld%lld", &n, &m)) {170 ac.init();171 for (int i = 0; i < n; ++i) {172 scanf("%s", buf);173 ac.insert(buf);174 }175 ac.build();176 Matrix mat = ac.get_Matrix();177 mat = pow_M(mat, m);178 ULL res = 0, ans = 0;179 for (int i = 0; i < mat.n; ++i) res += mat.mat[0][i];180 Matrix a = Matrix(2);181 a.mat[0][0] = 26, a.mat[1][0] = a.mat[1][1] = 1;182 a = pow_M(a, m);183 ans = a.mat[0][0] + a.mat[1][0];184 ans -= res;185 printf("%llu\n", ans);186 }187 return 0;188 }