文章目录

CF1753C Wish I Knew How to Sort 做题笔记

发布于

题意

给定长度为 $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() {
}

暂无评论

发表评论