yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P3715 魔法咒语 题解

发表于 更新于 分类于

P3715 魔法咒语 题解

题面

题目链接

解法

多模式字符串匹配首先想到AC自动机，那么将忌讳词语建立AC自动机，整个$dp$就有一维状态设为AC自动机的状态，另一维就用字符串的长度，得到$dp_{i,s}$表示长度为$i$，匹配到AC自动机的状态为$s$的字符串个数。转移时枚举基本词汇，在AC自动机上跑出下一个状态，判断是否合法然后向后转移。时间复杂度$O(Ln \Sigma)$，$\Sigma$为忌讳词语的总长度，可通过测试点$1-6$。

接下来分析如何做测试点$7-10$。发现测试点$7-10$有$|Si| \le 2$的性质（$|S_i|$为基本词汇长度），而$L \le 10^8$又给我们一个提示，即正解复杂度带有$\log L$，于是想到用矩阵快速幂来优化$dp$。考虑到因为有$|S_1| \le 2$，所以$dp{i,s}$只依赖于$dp_{i-2,t}$，就可以参考斐波那契数列的矩阵快速幂优化来设定一个$(tot \times 2) \times (tot \times 2)$，$tot$表示AC自动机状态总数（显然$tot \le \Sigma \le 100$）的转移矩阵处理即可。时间复杂度$O((\Sigma)^3 \log L)$，可通过测试点$7-10$。

综上所述，总的时间复杂度为$O(\min(Ln \Sigma, \Sigma^3 \log L))$。

AC代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/**
 * @file:           P3715.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P3715
*/
// #pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 205;
const int INFL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
void uadd(int &x, int y) {
    x += y;
    if (x >= MOD)
        x -= MOD;
}
struct matrix {
    int a[MAXN][MAXN], n;
    matrix(int m) {
        this->n = m;
        memset(a, 0, sizeof(a));
    }
    matrix operator*(const matrix &o) const {
        matrix ret(n);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    uadd(ret.a[i][j], a[i][k] * o.a[k][j] % MOD);
        return ret;
    }
};
struct ac_automaton {
    int nxt[MAXN][26], fail[MAXN], cnt[MAXN], tot;
    void insert(char *s) {
        int rt = 0;
        for (int i = 0; s[i]; ++i) {
            if (!nxt[rt][s[i] - 'a'])
                nxt[rt][s[i] - 'a'] = ++tot;
            rt = nxt[rt][s[i] - 'a'];
        }
        ++cnt[rt];
    }
    void build() {
        static queue<int> que;
        while (!que.empty())
            que.pop();
        for (int i = 0; i < 26; ++i)
            if (nxt[0][i])
                que.push(nxt[0][i]);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = 0; i < 26; ++i) {
                if (nxt[u][i]) {
                    fail[nxt[u][i]] = nxt[fail[u]][i];
                    que.push(nxt[u][i]);
                } else {
                    nxt[u][i] = nxt[fail[u]][i];
                }
            }
        }
    }
};
int n, m, k, sum, len[MAXN];
int dp[MAXN][MAXN];
char s[MAXN][MAXN], t[MAXN][MAXN];
ac_automaton ac;
inline int posi(int x, int l) {
    return sum * l + x + 1;
}
matrix qpow(matrix x, int y) {
    matrix ret(x.n);
    for (int i = 1; i <= x.n; ++i)
        ret.a[i][i] = 1;
    for (; y; y >>= 1, x = x * x)
        if (y & 1) ret = ret * x;
    return ret;
}
signed main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    for (int i = 1; i <= m; ++i)
        scanf("%s", t[i] + 1);
    for (int i = 1; i <= n; ++i)
        len[i] = strlen(s[i] + 1);
    for (int i = 1; i <= m; ++i)
        ac.insert(t[i] + 1);
    ac.build();
    if (k <= 100) {
        dp[0][0] = 1;
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j <= ac.tot; ++j) {
                if (ac.cnt[j])
                    continue;
                for (int x = 1; x <= n; ++x) {
                    int p = j;
                    for (int l = 1; l <= len[x]; ++l) {
                        p = ac.nxt[p][s[x][l] - 'a'];
                        int cnt = 0;
                        for (int o = p; o; o = ac.fail[o]) {
                            if (ac.cnt[o]) {
                                cnt += ac.cnt[o];
                                break;
                            }
                        }
                        if (cnt) {
                            p = -1;
                            break;
                        }
                    }
                    if (~p && i + len[x] <= k)
                        uadd(dp[i + len[x]][p], dp[i][j]);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= ac.tot; ++i)
            if (!ac.cnt[i])
                uadd(ans, dp[k][i]);
        write(ans), putchar('\n');
    } else {
        sum = ac.tot + 1;
        matrix base(sum * 2);
        for (int i = 0; i <= ac.tot; ++i)
            base.a[posi(i, 1)][posi(i, 0)] = 1;
        for (int i = 0; i <= ac.tot; ++i) {
            if (ac.cnt[i])
                continue;
            for (int x = 1; x <= n; ++x) {
                int p = i;
                for (int l = 1; l <= len[x]; ++l) {
                    p = ac.nxt[p][s[x][l] - 'a'];
                    int cnt = 0;
                    // ##sb-mistakes## AC自动机在做多模式匹配的时候**一定要跳fail指针**不然会**漏遍历很多东西**（AC自动机白学了）！！！
                    for (int o = p; o; o = ac.fail[o]) {
                        if (ac.cnt[o]) {
                            cnt += ac.cnt[o];
                            break;
                        }
                    }
                    if (cnt) {
                        p = -1;
                        break;
                    }
                }
                if (p == -1)
                    continue;
                if (len[x] == 1) {
                    uadd(base.a[posi(i, 0)][posi(p, 0)], 1);
                    // ##sb-mistakes## 写矩阵快速幂优化dp（尤其是dp[i]依赖于dp[i-2]这种）的时候一定要算好，不能重复加了
                    // uadd(base.a[posi(i, 1)][posi(p, 1)], 1);
                } else {
                    uadd(base.a[posi(i, 0)][posi(p, 1)], 1);
                }
            }
        }
        matrix tmp(sum * 2);
        tmp.a[1][posi(0, 0)] = 1;
        tmp = tmp * qpow(base, k);
        int ans = 0;
        for (int i = 0; i <= ac.tot; ++i)
            if (!ac.cnt[i])
                uadd(ans, tmp.a[1][posi(i, 0)]);
        write(ans), putchar('\n');
    }
    return 0;
}