2025 Summer Day21

Luogu-P13270 最小表示法

题意

给定一个长度为 $n$ 的字符串 $s$ ，求 $s$ 的最小表示法。

思路

首先如果暴力的话，复杂度是 $O(n^2)$ 的，但是我们发现如果我们当前已经发现了一个最小表示法，我们想要找到一个比这个还小的表示法，那么一定存在一个位置，使得这个位置上的字符不相等，根据这个就可以把复杂度优化到 $O(n)$ 。

提交记录：Link。

Luogu-P5357 AC自动机

题意

给定一个字符串 $s$ 和 $n$ 个模式串 $t_i$ ，求每个模式串在字符串 $s$ 中的出现次数。

思路

首先我们可以对 $s$ 建一个 AC 自动机，然后统计每个模式串在这个 AC 自动机的字典树上经过了那些节点，然后打标记。再建出 Fail 树，然后在 Fail 树上对标记求和。

提交记录：Link。

模拟题 - 嗑瓜子

题意

有一个人在嗑 $n$ 个瓜子，每次在瓜子中等概率拿出一个，有以下两种情况：

如果拿出的是瓜子，则吃掉，并把壳扔回瓜子中。
如果拿出的是壳，则将其丢弃。求他吃掉所有瓜子的期望。

思路

定义 $dp_{i,j}$ 表示有 $i$ 个瓜子和 $j$ 个壳的期望。根据题意写出转移即可。

Important：注意空间，因为 $j_{max}$ 可以达到 $2 \times n$ ，所以第二维要开到两倍。

Code

1
#include <iostream>
2
#define OnlineJudge
3

4
using std::cin;
5
using std::cout;
6

7
constexpr int MOD = 998244353;
8
constexpr int N = 4005;    // ! 注意两倍空间
9
long long dp[N][N];
10

11
long long QuickPow(long long base, long long pow) {
12
    long long result = 1;
13
    while (pow) {
14
        if (pow & 1) result = result * base % MOD;
15
        base = base * base % MOD;
16
        pow >>= 1;
17
    }
18
    return result;
19
}
20

21
int main() {
22
    std::ios::sync_with_stdio(false);
23
    cin.tie(nullptr);
24
    cout.tie(nullptr);
25

26
    int n;
27
    cin >> n;
28

29
    dp[n][0] = 1;
30

31
    for (int i = n - 1; i >= 0; i--) {
32
        for (int j = (n - i) * 2; j >= (i == 0 ? 2 : 0); j--) {
33
            if (i == 0) {
34
                dp[i][j] = QuickPow(j - 1, MOD - 2) * dp[i + 1][j - 2] % MOD;
35
            } else {
36
                if (j < 2) {
37
                    dp[i][j] = (j + 1) * QuickPow(i + j + 1, MOD - 2) % MOD * dp[i][j + 1] % MOD;
38
                } else if (j == (n - i) * 2) {
39
                    dp[i][j] = (i + 1) * QuickPow(i + j - 1, MOD - 2) % MOD * dp[i + 1][j - 2] % MOD;
40
                } else {
41
                    dp[i][j] = ((i + 1) * QuickPow(i + j - 1, MOD - 2) % MOD * dp[i + 1][j - 2] % MOD + (j + 1) * QuickPow(i + j + 1, MOD - 2) % MOD * dp[i][j + 1] % MOD) % MOD;
42
                }
43
            }
44
        }
45
    }
46

47
    #ifndef OnlineJudge
48
    for (int i = 0; i <= n; i++) {
49
        for (int j = 0; j <= 2 * (n - i); j++) {
50
            cout << dp[i][j] << ' ';
51
        }
52
        cout << '\n';
53
    }
54
    #endif
55

56
    long long answer = 0;
57
    for (int i = 1; i <= n * 2; i++) {
58
        answer = (answer + (3 * n - i) * dp[0][i] % MOD) % MOD;
59
    }
60

61
    cout << answer << '\n';
62

63
    return 0;
64
}