题意描述

给你一个 01 串，每次可以选择两个数字，当 $a i$$>$$a j$时进行交换， 反之不交换，无论交不交换都计入次数，让你求使得该串有序（从小到大）的期望次数。

思路
我们将串中数字$0$ 个数记为 $cnt$ 。

观察题意发现，我们只需要将前 $cnt$ 个数字全部交换成 $0$ 即可，且前 $cnt$ 个数字已经出现了$ w 个 0 $时，无论如何交换，都不会使得情况更劣（即不会出现 $0$ 的个数变少的情况，原因见题意加粗部分）。
我们用 $f i$表示前 $cnt$ 个数字中有 $i$ 个数字为 $0$ 的期望。

那么，问题就转化成了使得前 $cnt$个数字中多一个$0$ (当前已有 $i−1$ 个 $0$ )，期望的选择次数是多少？

我们知道，所有可能的交换方案数为：$C n2$，而只有前 $cnt$ 个数中的 $1$ 和后 $n−cnt+1$ 个数中的 $0$ 交换有意义。所以答案是
$(cnt−i+1) 2$$C n 2$。

那么 $f$ 数组的转移方程就是：

$f i ​ =f i−1 ​ +$ $(cnt−i+1) 2$ $C n 2​$

​

code:

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

int T;
const int L = 2e5 + 5;
int t, n, k, x, y, z, ans, cnt, fr, a[L];

int f[L];

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
		f = (ch == '-' ? -1 : f), ch = getchar();
	while (isdigit(ch))
		x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
	return x * f;
}

int qpow(int n, int m) {
	int ans = 1;
	while (m) {
		if (m & 1) {
			ans *= n;
			ans %= modn;
		}
		n *= n;
		n %= modn;
		m >>= 1;
	}
	return ans;
}

signed main() {
	T = read();
	while (T--) {
		cnt = 0, fr = 0;
		n = read();
		for (int i = 1; i <= n; i++) {
			a[i] = read();
			if (!a[i])
				cnt++;
		}
		for (int i = 1; i <= cnt; i++) {
			if (!a[i])
				fr++;
		}
		f[fr] = 0;
		for (int i = fr + 1; i <= cnt; i++) {
			f[i] = f[i - 1] + ((n * (n - 1) / 2) % modn) * qpow((cnt - i + 1) * (cnt - i + 1), modn - 2) % modn;
			f[i] %= modn;
		}
		cout << f[cnt] << endl;
	}
	return 0;
}