本文共 2670 字，大约阅读时间需要 8 分钟。
题意：
给出m个模式串，要求构造一长度为n的文本串，至少包括k种模式串，求有多少种可能的模式串。
k<=10 然后可以想到状压
一个文本串，k种模式串，很容易想到AC自动机。
把所有的模式串放入AC自动机上面，然后跑状压DP
跟AC自动机有关的DP一般都要用的AC自动机上的节点。
dp状态定义为dp[ i ][ j ][status]走到长度为i 时，在AC自动机上 j 这个节点
状态为 status 的方案数。
然后统计答案即可。
由于状态只与上一步有关，所以我滚动了一维，多开一维并不会MLE，也可以写。
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" = "< < << id); 80 } 81 82 void build() { 83 queue Q; 84 fail[root] = root; 85 for (int i = 0; i < 26; i++) 86 if (next[root][i] == -1) next[root][i] = root; 87 else { 88 fail[next[root][i]] = root; 89 Q.push(next[root][i]); 90 } 91 while (!Q.empty()) { 92 int now = Q.front(); 93 Q.pop(); 94 End[now] |=End[fail[now]]; 95 for (int i = 0; i < 26; i++) 96 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 97 else { 98 fail[next[now][i]] = next[fail[now]][i]; 99 Q.push(next[now][i]);100 }101 }102 }103 104 void debug() {105 for (int i = 0; i < cnt; i++) {106 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);107 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);108 printf("]\n");109 }110 }111 } ac;112 113 114 int main() {115 // FIN;116 while (~sfff(n, m, k)) {117 if (n == 0 && m == 0 && k == 0) break;118 ac.init();119 for (int i = 0; i < m; ++i) {120 scanf("%s", buf);121 ac.insert(buf, i);122 }123 ac.build();124 for (int i = 0; i <2; i++)125 for (int j = 0; j < ac.cnt; j++)126 for (int p = 0; p < (1 << m); p++)127 dp[i][j][p] = 0;128 int now = 0;129 dp[now][0][0] = 1;130 for (int i = 1; i <= n; ++i) {131 now = now ^ 1;132 for (int j = 0; j < ac.cnt; j++)133 for (int p = 0; p < (1 << m); p++)134 dp[now][j][p] = 0;135 for (int j = 0; j < ac.cnt; ++j) {136 for (int status = 0; status < (1 << m); ++status) {137 if (dp[now ^ 1][j][status]) {138 for (int l = 0; l < 26; ++l) {139 int st = (status | ac.End[ac.next[j][l]]);140 dp[now][ac.next[j][l]][st] = (dp[now][ac.next[j][l]][st] + dp[now ^ 1][j][status]) % mod;141 }142 }143 }144 }145 }146 LL ans = 0;147 for (int status = 0; status < (1 << m); ++status) {148 if (cal(status) < k) continue;149 for (int i = 0; i < ac.cnt; ++i)150 ans = (ans + dp[now][i][status]) % mod;151 }152 printf("%lld\n", ans);153 }154 return 0;155 }
转载于:https://www.cnblogs.com/qldabiaoge/p/11379082.html
