CF1753C Wish I Knew How to Sort Sol

喵喵题。考场上完全想不到。

很难想到把序列排序，得出最后的排序结果。

同时很难想到，原序列左半边的 \(1\) 会变成 \(0\)，右半边的 \(0\) 会变成 \(1\)。

很难想到这两部分的数量是一样的。

接着很难发现，对于倒数第 \(i\) 次交换，交换成功的概率是 \(p_i=\dfrac{i^2}{\dfrac{n(n-1)}{2}}\)。

上面是成功交换的方案数（此时左边剩下 \(i\) 个 \(1\)，右边剩下 \(i\) 个 \(0\)）。

下面是总选择方案数。反正随便选两个就行。

那么期望就是 \(\dfrac{1}{p_i}\)。答案就是 \(\sum\limits_{i=1}^{cnt}\dfrac{1}{p_i}\)没了。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10, Mod = 998244353;
int t, n, cntx, a[N];

inline int qpow(int bas, int pw) {
  int mul = 1; for (; pw; (bas *= bas) %= Mod, pw >>= 1)
    if (pw & 1) (mul *= bas) %= Mod; return mul;
} inline int inv(int x) { return qpow(x, Mod - 2); }

inline void solve() {
  cin >> n; cntx = 0;
  for (int i = 1; i <= n; ++i) cin >> a[i], cntx += !a[i];
  int cnt = 0; for (int i = 1; i <= cntx; ++i) cnt += a[i];
  int basc = n * (n - 1) / 2 % Mod;
  int res = 0; for (int i = 1; i <= cnt; ++i)
    (res += basc * inv(i * i % Mod) % Mod) %= Mod;
  cout << res << endl; return ;
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
  cin >> t; while (t--) solve(); return 0;
}

原文地址：http://www.cnblogs.com/MistZero/p/CF1753C-Sol.html