hubeikemi的个人博客
0%

牛客137448F

发表于 分类于
本文字数： 6.3k 阅读时长 ≈ 6 分钟

那我问你，你做过你牛叠的雷霆大DP吗？

牛客137448F-猴子排序的剪枝

题意

给定一个长度为 $n$ 的数组，每次随机抽取一个还没被选择的元素放入新数组末尾。如果出现前一个大于后一个，则清空新数组重新开始。求成功排序的期望操作次数。（可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$，为了避免精度问题，请直接输出整数$ \left(p \times q^{-1} \bmod M\right)$作为答案，其中 M = 998244353）

第一行输入一个整数 n (1 ≤ n ≤ 5000)
第二行输入 n 个整数 $a_1,a_2,\ldots,a_n \left( 1 \le a_i \le 10^9\right)$。

样例1：

1
2
3
4
5
6
输入
2
1 2

输出
4

样例2：

1
2
3
4
5
6
输入
3
1 1 2

输出
8

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
    
const int N = 5005;
const int MOD = 998244353;
int fact[N], invfact[N];

int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        b >>= 1LL;
        a = a * a % MOD;
    }
    return res;
}

int inv(int x) {
    return qmi(x, MOD - 2);
}
    
void solve(){
    
    int n; cin >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        ++mp[x];
    }

    vector<vector<int>> dp(n + 1, vector<int> (n + 1));
    dp[0][0] = 1;
    int i = 0, m = 0;
	
    // 最重要的一条：
    for (auto [val, c]: mp) {
        ++i;
        for (int j = 0; j <= m; ++j) {
            if (!dp[i - 1][j]) continue; // 注意这里别写错成dp[i][j]了，错了好几次。
            for (int k = 0; k <= c; ++k) {
                dp[i][j + k] = (dp[i][j + k] + (dp[i - 1][j] * invfact[k]) % MOD) % MOD;
            }
        }
        m += c;
    }
    
    int ans = 0;
    for (int l = 1; l <= n; ++l) {
        ans = (ans + dp[i][l] * fact[l] % MOD) % MOD;
    }
    cout << ans << '\n';
    
}
    
signed main(){
    
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    fact[0] = 1;
    for (int i = 1; i <= 5000; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invfact[5000] = inv(fact[5000]);
    for (int i = 4999; i >= 0; --i) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }

    int _ = 1;
    // cin >> _;
    while (_--)
    solve();
    return 0;
    
}

先说样例是怎么来的：

示例 1 分析 (输入 1 2)

设从头开始直到排序成功的总期望操作数为 $E$。

  • 情况 A (50% 概率)：先选 1，再选 2。

    操作 2 次，没有出现前一个元素大于后一个元素的情况。排序成功，结束。

    这部分的代价是：$2$

  • 情况 B (50% 概率)：先选 2，再选 1。

    插入 2（1次操作），再插入 1（第2次操作）。此时新数组是 [2, 1]，满足 $2 > 1$，本轮排序失败。

    此时你已经消耗了 2 次操作，并且一切从头开始。既然从头开始，后续还需要操作的期望次数依然是 $E$。

    这部分的代价是：$2 + E$

把它们加起来得到方程：

解这个方程：

这就是 $4$ 的由来。

示例 2 分析 (输入 1 1 2)

我们再推一下示例 2。全排列有 $A_3^3 = 6$ 种抽法，设总期望为 $E$：

  1. 抽到 1 1 2（2种情况，概率 $2/6 = 1/3$）：

    操作 3 次成功。代价：$3$

  2. 抽到 1 2 1（2种情况，概率 $1/3$）：

    前 2 次插入 1 和 2 是合法的，第 3 次插入 1 时发现 $2 > 1$，失败重来。消耗 3 次操作。

    代价：$3 + E$

  3. 抽到 2 1 1（2种情况，概率 $1/3$）：

    第 1 次插入 2 合法，第 2 次插入 1 时发现 $2 > 1$，立刻失败重来。仅仅消耗 2 次操作。

    代价：$2 + E$

列出方程：

核心结论：

对于这种“失败即重来”的模型，有一个通用的结论：

即 $E_{总} = \frac{E_{单轮操作}}{P_{单轮成功}}$，那么这题的本质就是一个推导并化简概率公式的数学题，最后用动态规划（或者说多项式乘法）来实现。

（注： 单轮操作步数 ($X$)： 这是指在某局游戏里（被清空之前），你一共塞了几个元素进去。比如你塞了 2 然后塞 1，挂了，这一局的 $X = 2$。 ）

1. 求分母：单轮成功的概率

假设原数组长度为 $n$，共有 $m$ 种不同的数字，第 $j$ 种数字出现的次数为 $c_j$。

成功概率 $P_n$：

一轮能成功，意味着抽出的 $n$ 个元素必须是不下降序列。也就是相同的数字必须挨在一起。

2.求分子：单轮期望操作数

一轮会在什么时候停止？要么失败停止，要么排满 $n$ 个成功停止。根据期望的线性性质（或者叫期望的尾部公式），操作 $X$ 次后结束的期望为：

这里如何理解？概率是怎么变成期望（次数）的？

我们要算的是“期望操作次数”。所以它的原始定义一定是：

我们把原始定义的公式拆开：

$E = 1 \times P(\text{恰好1次结束})$

$\quad\; + 2 \times P(\text{恰好2次结束})$

$\quad\; + 3 \times P(\text{恰好3次结束})$

$\quad\; + 4 \times P(\text{恰好4次结束})$

$\quad\; + \dots$

我们把它写成加法，排成一个三角形阵列：

原本我们是横着一行一行加的。

如果现在我们竖着一列一列加

  • 第 1 列：$P(\text{恰好1次}) + P(\text{恰好2次}) + P(\text{恰好3次}) + \dots$

    所有的概率全加起来，等于多少？等于 $100\%$ ($1$)！因为游戏总要在某一次结束，也就是必定能跨过 $0$ 步，迈出第 $1$ 步。即 $P(X > 0)$。

  • 第 2 列：$P(\text{恰好2次}) + P(\text{恰好3次}) + P(\text{恰好4次}) + \dots$

    这是什么意思？意思是游戏在第 $1$ 次没有结束，至少撑到了第 2 次及以上。这不就是 $P(\text{前 1 个元素合法})$ 吗！也就是 $P(X > 1)$。

  • 第 3 列：$P(\text{恰好3次}) + P(\text{恰好4次}) + \dots$

    意思是游戏至少撑到了第 3 次及以上，即 $P(\text{前 2 个元素合法})$，也就是 $P(X > 2)$。

所以，把每一列的和加起来，公式就变成了：

即：

等价于：

设前 $k$ 个元素合法的概率为 $P_k$。要让前 $k$ 个元素合法，我们需要从第 $j$ 种数字中抽出 $x_j$ 个，满足 $\sum x_j = k$，且 $0 \le x_j \le c_j$。

抽出这些数字并排列合法的概率是：

怎么求的？

核心思想就是最基础的古典概型公式：

1. 分母：总的抽取方案数

从 $n$ 个元素中，依次抽出 $k$ 个元素。

因为我们把所有元素都看作不同的个体，并且是有顺序地一个个抽，这本质上是一个排列问题。

总方案数为从 $n$ 中取 $k$ 的排列数：$A_n^k = \frac{n!}{(n-k)!}$

2. 分子：合法的抽取方案数

什么样的抽取方案是“合法”的？不下降。

既然要求不下降，意味着这 $k$ 个元素被抽出来后，它们的相对位置已经被彻底锁死了。所有的 1 必须排在所有的 2 前面，所有的 2 必须排在所有的 3 前面，依此类推。

假设在这 $k$ 个位置中，我们决定放入 $x_1$ 个第一种数字、$x_2$ 个第二种数字…… $x_m$ 个第 $m$ 种数字（$x$ 可以取0）。

对于第 $j$ 种数字：

从 $c_j$ 个数字中抽出 $x_j$ 个并排列的方案数为：$A_{c_j}^{x_j} = \frac{c_j!}{(c_j - x_j)!}$

因为每种数字的抽取是互相独立的，根据乘法原理，对于一种特定的数量分配 $(x_1, x_2, \dots, x_m)$，合法的抽取方案数为：

这只是其中一种数量分配的方案数。由于我们可以在满足 $\sum x_j = k$ 的前提下，任意分配这 $k$ 个名额，所以需要把所有可能的分配情况累加起来。

这就是求和符号的来源：

合并公式

现在我们把分子和分母组合起来：

把分母 $A_n^k$ 替换为 $\frac{n!}{(n-k)!}$ ，得到了 $P_k$ 最终公式：

3. 化简

现在我们把总期望公式写出来：

把 $P_k$ 和 $P_n$ 代入，$ 会被约掉：

化简后只剩：

变量代换

设 $y_j = c_j - x_j$。既然 $\sum x_j = k$，那么 $\sum y_j = \sum c_j - \sum x_j = n - k$。

再设 $l = n - k$。当 $k$ 从 $0$ 遍历到 $n-1$ 时，$l$ 正好从 $n$ 遍历到 $1$。

公式变成：

所以这题只和数组大小 $n$，和数的种数量 $m$ 有关。

4. 转化为DP / 多项式思路（仙术）

仔细看后面这一坨：$\sum_{\sum y_j = l} \prod_{j=1}^m \frac{1}{y_j!}$

这不就是多项式乘法展开后的系数吗？！所以，我们为了让“想算的式子”变成“多项式乘法”，要怎么做？ 直接让多项式里的系数 $A_y$ 和 $B_y$，等于 $\frac{1}{y!}$ 不就行了！

它完全等价于：将 $m$ 个多项式 $A_j(x) = \sum_{y=0}^{c_j} \frac{1}{y!} x^y$ 乘起来，结果中 $x^l$ 的系数！

这里 前面的系数 $\frac{1}{y!}$ 才是本体，它是我们真正需要相乘并累加的数值。 把它们绑定在一起写成 $\frac{1}{y!} x^y$，是为了白嫖“多项式乘法合并同类项”的规则，让计算机用两层 for 循环就能搞定原本极其复杂的全排列求和。

因为题目 $N \le 5000$，$O(N^2)$ 的算法完全可以跑过。我们根本不需要上 NTT，直接用背包 DP 的思路做多项式乘法即可。

代码实现框架 (C++)：

  1. 统计每个数字出现的频次 $c_j$。
  2. 预处理阶乘及其逆元（模 $998244353$）。
  3. 设 dp[i] 表示多项式乘积中 $x^i$ 的系数。初始 dp[0] = 1。
  4. 遍历每一个频次 $c$：
    • dp[i][j + k] = (dp[i][j + k] + dp[i - 1][j] * invFact[k]) % MOD;
  5. 最终答案就是 $\sum_{l=1}^n (l! \times dp[m][l]) \pmod{998244353}$。

关键代码：

1
2
3
4
5
6
7
8
9
10
for (auto [val, c]: mp) {
    ++i;
    for (int j = 0; j <= m; ++j) {
        if (!dp[i - 1][j]) continue;
        for (int k = 0; k <= c; ++k) {
            dp[i][j + k] = (dp[i][j + k] + (dp[i - 1][j] * invfact[k]) % MOD) % MOD;
        }
    }
    m += c;
}

这题总算结束了，哦对了。