题解：AT_abc360_e [ABC360E] Random Swaps of Balls

· · 题解

[ABC360E] Random Swaps of Balls 题解

题意

有 N - 1 个白球和一个黑球。这些 N 球排列成一排，黑球最初位于最左边的位置。

高桥正好要执行下面的操作 K 次。

经过 K 次操作后，让黑球位于左边第 x 个位置。求 x 的期望值，对 998244353 取模。

思路

记 k 次操作后黑球在最左边的概率为 f，则黑球在其他点的概率均为 \frac{1-f}{n-1}。

因为若黑球不在最左边，在其他点的概率都相同。

求出 f 即可求出答案。

设 f_i 表示第 i 次操作后黑球在最左边的概率。

记 p 为黑球从最左边跑到其他点的概率。

记 q 为黑球从其他点回到最左边的概率。

p=2\times \frac{1}{n}\times\frac{n-1}{n}=\frac{2n-2}{n^2} q=2\times \frac{1}{n} \times \frac{1}{n}=\frac{2}{n^2}

注意每次操作所选的 a 和 b 顺序没有影响，概率需要乘二。

状态转移：

f_i=(1-p)f_{i-1}+q(1-f_{i-1})

即保持在最左边的概率加上从其他点回到最左边的概率。

时间复杂度 O(k)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int mod = 998244353;
int qpow(int a, int x) {
    int ret = 1;
    for (; x; x >>= 1, a = a * a % mod)
        if (x & 1) ret = ret * a % mod;
    return ret;
}
int inv(int x) {return qpow(x, mod - 2);}
int n, k, p, q, e, ans, dp[N];
signed main() {
    cin >> n >> k;
    p = 2 * (n - 1) % mod * inv(n * n % mod) % mod; 
    q = 2 * inv(n * n % mod) % mod;
    dp[0] = 1;
    for (int i = 1; i <= k; i ++)
        dp[i] = (1 - p + mod) % mod * dp[i - 1] % mod + q % mod * (1 - dp[i - 1]) % mod,
        dp[i] += mod, dp[i] %= mod;
    ans += dp[k];
    e = (1 - dp[k] + mod) % mod * inv(n - 1) % mod;
    e *= (n - 1) % mod * (n + 2) % mod * inv(2) % mod;
    e %= mod;
    ans += e, ans %= mod;
    cout << ans << endl;
    return 0;
}