Walk Through Squares HDU - 4758 AC自动机+简单状压DP-白红宇

Walk Through Squares HDU - 4758 AC自动机+简单状压DP

阅读量：5030 次

发布时间：2019-06-12

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

题意：给你两个串，求用m个R，n个D能组成多少个包含这两个串

题解：先构造一个AC自动机记录每个状态包含两个串的状态，

状态很容易定义 dp【i】【j】【k】【status】表示在AC自动机K这个节点

使用了 i 个D,j个R ，状态为status的方案数。

然后直接DP即可。

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" = "<
                   
                    <
                    
                     << id); 84 } 85 86 void build() { 87 queue
                     
                       Q; 88 fail[root] = root; 89 for (int i = 0; i < 2; i++) 90 if (next[root][i] == -1) next[root][i] = root; 91 else { 92 fail[next[root][i]] = root; 93 Q.push(next[root][i]); 94 } 95 while (!Q.empty()) { 96 int now = Q.front(); 97 Q.pop(); 98 End[now] |= End[fail[now]]; 99 for (int i = 0; i < 2; i++)100 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];101 else {102 fail[next[now][i]] = next[fail[now]][i];103 Q.push(next[now][i]);104 }105 }106 }107 108 LL solve() {109 mem(dp, 0);110 dp[0][0][0][0] = 1;111 for (int i = 0; i <= n; ++i) {112 for (int j = 0; j <= m; ++j) {113 for (int k = 0; k < cnt; ++k) {114 for (int status = 0; status < 4; ++status) {115 if (dp[i][j][k][status] == 0) continue;116 for (int l = 0; l < 2; ++l) {117 int idx = next[k][l];118 if (l == 0) {119 dp[i + 1][j][idx][status | End[idx]] =120 (1LL * dp[i + 1][j][idx][status | (End[idx])] + 1LL * dp[i][j][k][status]) %121 mod;122 // printf("i = %d j = %d idx = %d status = %d dp = %lld\n", i + 1, j, idx,123 // status | (End[idx]),124 // dp[i + 1][j][idx][status | End[idx]]);125 } else {126 dp[i][j + 1][idx][status | End[idx]] =127 (1LL * dp[i][j + 1][idx][status | End[idx]] + 1LL * dp[i][j][k][status]) % mod;128 // printf("i = %d j = %d idx = %d status = %d dp = %lld\n", i, j + 1, idx,129 // status | (End[idx]),130 // dp[i][j + 1][idx][status | End[idx]]);131 }132 }133 }134 }135 }136 }137 LL ans = 0;138 for (int i = 0; i < cnt; ++i) ans = (ans + dp[n][m][i][3]) % mod;139 return ans;140 }141 142 void debug() {143 for (int i = 0; i < cnt; i++) {144 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);145 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);146 printf("]\n");147 }148 }149 } ac;150 151 int main() {152 // FIN;153 sfi(T);154 while (T--) {155 sffi(m, n);156 ac.init();157 for (int i = 0; i < 2; ++i) {158 sfs(buf);159 ac.insert(buf, i);160 }161 ac.build();162 printf("%lld\n", ac.solve());163 }164 return 0;165 }