「Codeforces 1753C」Wish I Knew How to Sort - 概率与期望

发表于 分类于 ， 阅读次数： Disqus：

题意描述

Codeforces 链接

你有一个只含 \(0\) 和 \(1\) 的 \(n\) 位序列，你需要将这个序列排序。对于这个序列，你每次可以随机地选择两个数进行交换，求将这个序列排好序所交换次数的期望 \(\mod 998244353\)。

解题思路

本题求的是期望步数，可考虑使用 DP 解决。我们统计这个序列中有 \(\text{cnt}\) 个 \(0\)，于是这个问题可以转化为将所有的 \(0\) 移动到前 \(\text{cnt}\) 位需要的步数的期望。我们设 \(f_i\) 表示前 \(\text{cnt}\) 位有 \(i\) 个 \(0\) 的情况下排好序所需要的期望步数，显然 \(f_\text{cnt} = 0\)。如果我们将 \(f_i\) 状态变化为 \(f_{i + 1}\) 状态，我们需要将前 \(\text{cnt}\) 位中的一个 \(1\) 和后 \(\text{n - cnt}\) 位的一个 \(0\) 进行交换。选出这对的概率为 \(p = \frac{(\text{cnt} - i) \times (\text{cnt} - i)}{ \frac{n \times (n - 1)}{2} } = \frac{2 \times (\text{cnt} - i)^2}{n \times (n - 1)}\)。于是我们可以通过期望的线性性质得到以下的状态转移方程：

\[ \begin{align*} f_i &= p \times f_{i + 1} + (1 - p) \times f_i + 1 \\ f_i &= f_{i + 1} + \frac{n \times (n - 1)}{2 \times (\text{cnt} - i)^2} \end{align*} \]

状态转移方程的除法可以用快速幂求逆元解决。最后我们统计原序列中前 \(\text{cnt}\) 项中有 \(\text{now}\) 个 \(0\)，答案即为 \(f_\text{now}\)。时间复杂度为 \(O(kn), k = \log 998244353\)

代码演示

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
#include <cstdio>
#include <vector>

const int MOD = 998244353;

inline long long pow(const int n, const int k) {
    long long ans = 1;
    for (long long num = n, t = k; t; num = num * num % MOD, t >>= 1) {
        if (t & 1) {
            ans = ans * num % MOD;
        }
    }
    return ans;
}

void solve() {
    int n;
    scanf("%d", &n);

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int cnt = 0, now = 0;
    for (int i = 0; i < n; i++) if (a[i] == 0) cnt++;
    for (int i = 0; i < cnt; i++) if (a[i] == 0) now++;

    std::vector<long long> f(cnt + 1);
    f[cnt] = 0;

    for (int i = cnt - 1; i >= 0; i--) {
        f[i] = (f[i + 1] + (1ll * n * (n - 1) % MOD * pow(2, MOD - 2) % MOD * pow(cnt - i, MOD - 2) % MOD * pow(cnt - i, MOD - 2) % MOD)) % MOD;
    }

    printf("%lld\n", f[now]);
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}