详细题解

1. 问题转化

设数组最终排序后，前 $k$ 个位置应该是 $0$，后 $n-k$ 个位置应该是 $1$，其中 $k$ 是原数组中 $0$ 的个数。定义“错位”为：在前 $k$ 个位置中出现了 $1$，或在后 $n-k$ 个位置中出现了 $0$。由于 $0$ 的总数固定，前 $k$ 个位置中 $1$ 的个数等于后 $n-k$ 个位置中 $0$ 的个数，记这个数为 $x$。

每次操作随机选择一对 $(i,j)$（$i<j$）。只有当 $i$ 在前 $k$ 个位置且 $a_i=1$，同时 $j$ 在后 $n-k$ 个位置且 $a_j=0$ 时，交换才会使 $x$ 减少 $1$（因为一个 $1$ 从前半部分移到后半部分，一个 $0$ 从后半部分移到前半部分）。其他所有情况（包括 $i,j$ 都在同一部分，或顺序正确）都不会改变 $x$。

2. 概率计算

总共有 $\binom{n}{2}$ 个无序对。满足上述条件的有效对数为 $x \cdot x = x^2$（因为前半部分有 $x$ 个 $1$，后半部分有 $x$ 个 $0$，且由于前半部分索引均小于后半部分，所有这样的对都满足 $i<j$）。因此，在一次操作中，$x$ 减少 $1$ 的概率为

$$p_x = \frac{x^2}{\binom{n}{2}}.$$

3. 期望步数

设 $E[x]$ 表示当前有 $x$ 个错位时，还需要操作的期望次数。显然 $E[0]=0$。对于 $x>0$，有

$$E[x] = 1 + (1-p_x)E[x] + p_x E[x-1].$$

解得

$$E[x] = \frac{1}{p_x} + E[x-1] = \frac{\binom{n}{2}}{x^2} + E[x-1]. $$

递推可得

$$E[x] = \binom{n}{2} \sum_{i=1}^{x} \frac{1}{i^2}.$$

4. 模运算

答案需要输出模 $998244353$ 下的值。由于模数是质数，我们可以用逆元计算分数：

$$\text{ans} = \binom{n}{2} \cdot \sum_{i=1}^{x} \text{inv}(i^2) \pmod{MOD}, $$

其中 $\text{inv}(i)$ 是 $i$ 的模逆元。

5. 预处理

因为所有测试用例的 $n$ 之和不超过 $2\times 10^5$，我们可以预处理 $1$ 到 $2\times 10^5$ 的逆元，再计算平方逆元，并求出前缀和 $\text{pref}[x] = \sum_{i=1}^{x} \text{inv}(i^2)$。这样每个测试用例可以 $O(1)$ 得到答案。

6. 算法步骤

1. 预处理逆元数组 inv[1..MAXN]，平方逆元 inv2[i] = inv[i] * inv[i] % MOD，前缀和 pref[i] = (pref[i-1] + inv2[i]) % MOD。
2. 对于每个测试用例：
   • 读入 $n$ 和数组 $a$。
   • 统计 $0$ 的个数 $k$。
   • 统计前 $k$ 个元素中 $1$ 的个数 $x$。
   • 若 $x=0$，输出 $0$。
   • 否则计算 $\binom{n}{2} = n(n-1)/2 \bmod MOD$，再乘以 $\text{pref}[x]$，输出结果。

7. 复杂度

预处理 $O(\text{MAXN})$，每个测试用例 $O(n)$ 统计，总复杂度 $O(\sum n)$，满足要求。

8. 样例验证

• 样例1：$n=3, k=2, x=1$，$\binom{3}{2}=3$，$\sum_{i=1}^{1}1/i^2=1$，答案 $3$。
• 样例2：$x=0$，答案 $0$。
• 样例3：$n=6, k=2, x=2$，$\binom{6}{2}=15$，$\sum_{i=1}^{2}1/i^2 = 1+1/4 = 5/4$，$15 \times 5/4 = 75/4$，模意义下为 $75 \times 4^{-1} \bmod 998244353 = 249561107$，符合输出。

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

const int MOD = 998244353;
const int MAXN = 200000;

int inv[MAXN + 5], inv2[MAXN + 5], pref[MAXN + 5];

void precompute() {
   inv[1] = 1;
   for (int i = 2; i <= MAXN; ++i) {
       inv[i] = MOD - 1LL * (MOD / i) * inv[MOD % i] % MOD;
   }
   for (int i = 1; i <= MAXN; ++i) {
       inv2[i] = 1LL * inv[i] * inv[i] % MOD;
       pref[i] = (pref[i - 1] + inv2[i]) % MOD;
   }
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   precompute();
   int t;
   cin >> t;
   while (t--) {
       int n;
       cin >> n;
       vector<int> a(n);
       int cnt0 = 0;
       for (int i = 0; i < n; ++i) {
           cin >> a[i];
           if (a[i] == 0) ++cnt0;
       }
       int x = 0;
       for (int i = 0; i < cnt0; ++i) {
           if (a[i] == 1) ++x;
       }
       if (x == 0) {
           cout << "0\n";
           continue;
       }
       long long pairs = 1LL * n * (n - 1) / 2 % MOD;
       int ans = pairs * (long long)pref[x] % MOD;
       cout << ans << '\n';
   }
   return 0;
}