[JSOI 2007] 文本生成器

发表于2017-04-16更新于2020-08-06

题目大意

给定词典 DD 与文章长度 mm，称一篇文章是可读的当且仅当其中包含了至少一个来自于词典中的词，文章、单词由大写英文字母组成。求可读文章的篇数，答案对 10,00710,007 取模。

1⩽∣D∣⩽601 \leqslant |D| \leqslant 60

1⩽len⩽1001 \leqslant len \leqslant 100

题目链接

【JSOI 2007】文本生成器 - Luogu 4052

题解

建立 AC 自动机。

答案不方便直接计算，考虑答案的对立面——不可读文章的篇数，记 f[i,  j]f[i, \; j] 表示到达了 AC 自动机上的节点 jj、文章已经考虑了 ii 个字符时，不可读文章的篇数。转移时，枚举考虑的字符数 ii，再枚举每一个节点 jj，枚举当前字符 cc，若 AC 自动机上节点 jj 再加上字符 cc 不是单词节点，则进行转移，把 f[i,  j]f[i, \; j] 的答案加上 f[i−1,  node(j+c)]f[i - 1, \; node(j + c)]（对于那个 node(j+c)node(j + c)，会意即可。。。）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
const int MAXN = 60;
const int MAXM = 105;
const int CHARSET_SIZE = 'Z' - 'A' + 1;
const char BASE_CHAR = 'A';
const int MOD = 10007;
struct Trie {
    struct Node {
        Node *c[CHARSET_SIZE], *fail, *next;
        int id;
        bool isWord;
        Node (bool isWord = false) : isWord(isWord), fail(NULL), next(NULL) {
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }
    } *root;
    Trie() : root(NULL) {}
    void insert(char *begin, char *end) {
        Node **u = &root;
        for (char *p = begin; p != end; p++) {
            if (!(*u)) *u = new Node();
            u = &(*u)->c[*p];
        }
        if (!(*u)) *u = new Node(true);
        else (*u)->isWord = true;
    }
    void build() {
        std::queue<Node *> q;
        q.push(root);
        root->fail = root;
        root->next = NULL;
        while (!q.empty()) {
            Node *u = q.front();
            q.pop();
            for (int i = 0; i < CHARSET_SIZE; i++) {
                Node *c = u->c[i];
                if (!c) continue;
                Node *v = u->fail;
                while (v != root && !v->c[i]) v = v->fail;
                c->fail = u != root && v->c[i] ? v->c[i] : root;
                c->next = c->fail->isWord ? c->fail : c->fail->next;
                q.push(c);
            }
        }
    }
    bool next(Node *u, int ch, Node *&next) {
        while (u != root && !u->c[ch]) u = u->fail;
        next = u->c[ch] ? u->c[ch] : root;
        if (!u->c[ch]) return false;
        else if (u->c[ch]->isWord) return true;
        else if (u->c[ch]->next) return true;
        else return false;
    }
    void getNodeList(std::vector<Node *> &vec) {
        std::queue<Node *> q;
        q.push(root);
        while (!q.empty()) {
            Node *u = q.front();
            q.pop();
            vec.push_back(u);
            for (int i = 0; i < CHARSET_SIZE; i++) if (u->c[i]) q.push(u->c[i]);
        }
    }
} t;
int pow(int a, int n) {
    int res = 1;
    for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
    return res % MOD;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        static char str[MAXM];
        scanf("%s", str);
        int len = strlen(str);
        for (int i = 0; i < len; i++) str[i] -= BASE_CHAR;
        t.insert(str, str + len);
    }
    t.build();
    std::vector<Trie::Node *> vec;
    t.getNodeList(vec);
    static int f[MAXM][MAXN * MAXM];
    for (int i = 0; i < vec.size(); i++) vec[i]->id = i, f[0][i] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < vec.size(); j++) {
            for (int k = 0; k < CHARSET_SIZE; k++) {
                Trie::Node *next;
                if (!t.next(vec[j], k, next)) (f[i][j] += f[i - 1][next->id]) %= MOD;
            }
        }
    }
    printf("%d\n", ((pow(CHARSET_SIZE, m) - f[m][t.root->id] % MOD) + MOD) % MOD);
    return 0;
}