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

于是可以递推，\(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;}