「CTS2019」重复

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

LOJ 3123

给个串 $s$，求有多少个长为 $m$ 的串，无限次重复后能找到一个长为 $|s|$ 的字典序小于 $s$ 的子串。
小写字母，$|s|, m\le 2000$。

主要思路

设 $n = |s|$ 与 $m$ 同阶。看到 rqy 的题解搞了一个 $O(n\operatorname{poly}(n))$ 的做法，然后我比较菜没看懂，于是采用了比较多人用的 kmp 做法。

首先给 $s$ 建 kmp 自动机，考虑把一个串 $t$ 扔到上面跑，判断是否合法。
发现加入一个字符 $c$ 时，如果当前位置的 fail 树上的祖先存在一个点的下一个位置大于 $c$，直接返回合法。

所以考虑统计不合法串的个数。

此时自动机变成这样：对于每个点，存在一个字符 $c$，使得下一个字符是 $c$ 时会指向某个位置，大于 $c$ 时会指向原点，小于 $c$ 时则转移不存在。

考虑一个不合法串 $t$，若其重复足够多次后在自动机上匹配到状态 $pos$，那么走 $m$ 步仍然会回到 $pos$。

于是可以求出 $dp(i, j)$ 表示从原点走 $i$ 步走到 $j$ 的方案数，然后枚举位置 $pos$，枚举走了几步才第一次走到原点，然后用 dp 数组计算答案。

复杂度 $O(nm)$。

这种东西场上我一辈子都想不出来罢

参考代码

细节见代码。

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
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef long long i64;
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define mod 998244353
inline int ksm(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1)
            res = 1ll * res * x % mod;
    return res;
}
inline void qmo(int &x){ x += x >> 31 & mod; }
} // namespace my_std
using namespace my_std;

#define N 2020
int n, m, ans;
char s[N];
int nxt[N], to[N], mx[N];
int f[N][N], g[N][N], len;

inline void build(){
    Rint j(0);
    for(Rint i = 2; i <= n;){
        while(j && s[i] != s[j + 1]) j = nxt[j];
        if(s[i] == s[j + 1]) ++j;
        nxt[i++] = j;
    }
    for(Rint i = 0; i <= n; ++i){
        Rint k(i == n ? nxt[i] : i);
        mx[i] = s[k + 1] - 97;
        to[i] = k + 1;
        while(k){
            k = nxt[k];
            if(chkmax(mx[i], s[k + 1] - 97)) to[i] = k + 1;
        }
        if(to[i] != i + 1) len = i - to[n = i] + 1;
    }
}

int main() {
    scanf("%d%s", &m, s + 1);
    n = strlen(s + 1);
    build();
    f[0][0] = 1;
    FOR(i, 1, m) FOR(j, 0, n){
        qmo(f[i][to[j]] += f[i - 1][j] - mod);
        qmo(f[i][0] += (25ll - mx[j]) * f[i - 1][j] % mod - mod);
    }
    FOR(i, 0, n) g[1][i] = 25 - mx[i];
    FOR(i, 2, m) FOR(j, 0, n) g[i][j] = g[i - 1][to[j]];
    Rint ans(!(m % len) ? len : 0);
    FOR(i, 0, m) FOR(j, 0, n) qmo(ans += (i64)f[i][j] * g[m - i][j] % mod - mod);
    qmo(ans = ksm(26, m) - ans);
    printf("%d\n", ans);
    return 0;
}