Div. 2 Codeforces Round #829 A-E( 二 ) _生活百科

E题解知识点：概率dp 。
设 \(f[i]\) 代表将 \(i\) 个还没排好的 \(1\) （如 1100101 有 \(2\) 个 \(1\) 没排好）排好的期望步数。
对于 \(f[i]\)，下一步排好一个 \(1\) （即到达 \(i-1\) 状态）的概率是 \(\dfrac{i^2}{C_n^2}\)，下一步啥都没变的概率就是 \(1-\dfrac{i^2}{C_n^2}\)，于是有：
\[\begin{aligned} f[i] &= (f[i-1]+1) \cdot \dfrac{i^2}{C_n^2} + (f[i]+1) \cdot (1-\dfrac{i^2}{C_n^2})\\ \dfrac{i^2}{C_n^2} \cdot f[i] &= \dfrac{i^2}{C_n^2} \cdot f[i-1] + 1\\ f[i] &= f[i-1] + \dfrac{C_n^2}{i^2}\end{aligned}\]即一步到达 \(i-1\) 后再排完的期望乘这步的概率加一步啥也没干的期望乘这步的概率就是 \(f[i]\)。
于是可以递推，\(f[0] = 0\)，求的是 \(f[cnt1]\)，\(cnt1\) 是初始没排好 \(1\) 的个数。

这里其实有个概率论的定理：如果一个事件的结果A发生的概率是 \(P\)，则一直做这件事直到第一次发生结果A的期望 \(X\) 是 \(\dfrac{1}{P}\)。
证明：
\[\begin{aligned} X &= 1\cdot P+(X+1)\cdot (1-P)\\ P\cdot X &= 1\\ X &= \frac{1}{P}\end{aligned}\]

时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码

#include <bits/stdc++.h>#define ll long longusing namespace std;const int mod = 998244353;int a[200007];ll qpow(ll a, ll k) {ll ans = 1;while (k) {if (k & 1) ans = (ans * a) % mod;k >>= 1;a = (a * a) % mod;}return ans;}bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];int cnt0 = count(a + 1, a + n + 1, 0);int cnt1 = count(a + 1, a + cnt0 + 1, 1);int c2 = 1LL * n * (n - 1) / 2 % mod;int ans = 0;for (int i = 1;i <= cnt1;i++) {ans = (ans + 1LL * c2 * qpow(1LL * i * i % mod, mod - 2) % mod) % mod;}cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}