落谷 P4052 [JSOI2007]文本生成器

题目链接。只要有一个可读就行，容斥会好做一点。

可读数量 \(=\) 总数 \(-\) 不可读数量

总数显然是 \(26 ^ n\)。

求解不可读数量

不可读数量可以利用 AC 自动机的模型进行 DP，把 \(AC\) 自动机上所有串的终点及他们在 fail 树上的子树全部染上非法，这样即求在 AC 自动机上走 \(m\) 步，不经过非法点的方案数？

朴素 \(DP\) （或者说递推的思想）：

\(f[i][j]\) 表示前 \(i\) 个字符，当前在 AC 自动机上的节点编号是 \(j\) 的方案数。

设 \(u\) 点走一步能到 \(v\)，显然：\(f[i][v] = \sum f[i - 1][u]\)。

复杂度 \(O(2600MN)\) 即 \(2600 * 6000\) 差不多 \(1e7\) 的亚子轻松跑过。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int L = 6005, M = 105, S = 26, P = 10007;
int n, m, q[L], f[M][L], tr[L][S], idx, fail[L];
bool e[L];
char s[M];
void insert() {
    int len = strlen(s + 1), p = 0;
    for (int i = 1; i <= len; i++) {
        int ch = s[i] - 'A';
        if (!tr[p][ch]) tr[p][ch] = ++idx;
        p = tr[p][ch];
    }
    e[p] = true;
}
void build() {
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) q[++tt] = tr[0][i];
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = 0; i < 26; i++) {
            int v = tr[u][i];
            if (v) {
                fail[v] = tr[fail[u]][i];
                if (e[fail[v]]) e[v] = true;
                q[++tt] = v;
            } else tr[u][i] = tr[fail[u]][i];
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        insert();
    }
    build();
    f[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int u = 0; u <= idx; u++) {
            if (e[u] || !f[i][u]) continue;
            for (int k = 0; k < 26; k++) {
                int v = tr[u][k];
                if (e[v]) continue;
                (f[i + 1][v] += f[i][u]) %= P;
            }
        }
    }
    int ans = 1;
    for (int i = 1; i <= m; i++) ans = ans * 26 % P;
    for (int i = 0; i <= idx; i++)
        if (!e[i]) ans = (ans - f[m][i] + P) % P;
    printf("%d\n", ans);
    return 0;
}

落谷 P4052 [JSOI2007]文本生成器

原文：https://www.cnblogs.com/dmoransky/p/12419262.html