题意
给定长度为 $n$ 的 01 串 $a$,并以如下方式排序:
每次随机选定 $i$ 和 $j$,满足 $i < j$,如果 $a_i > a_j$,就交换 $a_i$ 和 $a_j$,否则什么也不干。
问期望操作次数,对 $998244353$ 取模。
$1 \leq n \leq 2 \times 10^5$
题解
假设一共有 $k$ 个 0,前 $k$ 位里有 $x$ 个 1,那么后 $n - k$ 位里就会有 $x$ 个 0。
最终状态下,前 $k$ 位是 0,后 $n - k$ 位是 1。那么一次有效的操作是把前 $k$ 位的一个 1,和后 $n - k$ 位的一个 0 交换了。
在这样的情况下,一次操作中有效的概率是 $\dfrac{x^2}{n(n - 1)/ 2}$,期望次数就是它的倒数。
答案即为
$$ \sum\limits_{i = 1}^x \frac{n(n - 1)/2}{x^2} $$
代码
constexpr tp mod = 998244353;
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, tar = 0; bin >> n;
vector<tp> a(n);
bin.rar(FULL(a));
tp cnt = count_if(FULL(a), [](tp x) { return !x; }), x = 0;
for (tp i = 0; i < cnt; ++i) x += a[i];
for (tp i = 1; i <= x; ++i) tar = (tar + n * (n - 1) / 2 % mod * lib::inverse(i * i, mod)) % mod;
bin << tar << '\n';
}
void MIST() {
}