鲜花
被卡了一万年。
考虑过序列变换的各种情况和逆序对，结果这俩情况状态太多，而且相同逆序对 ans 也不一定相同。/ll
sol
我们最后想要的状态为所有 \(0\) 都在 \(1\) 的左边，令 \(cnt_0\) 为 \(0\) 的个数，\(cnt_1\) 为 \(1\) 个数。
\(cnt_0+cnt_1=n\)，结束的状态前 \(cnt_0\) 个数均为 \(0\)，后 \(cnt_1\) 个数均为 \(1\)。
其余状态会有 \(0\) 混入后 \(cnt_1\) 个数中，\(1\) 混入前 \(cnt_0\) 个数中，可以视作由结束的状态交换得到，这些 \(0\) 与 \(1\) 的数量是等价的，记为 \(m\)。
将前 \(cnt_0\) 个数和后 \(cnt_1\) 个数视为两部分，其内部的交换不能影响 \(m\)，而结束的状态即 \(m\) 为 \(0\)，每次进行交换要么不影响 \(m\)，要么将 \(m\) 减 \(1\)，我们进行分类讨论后在这个思路上进行转移。
思路卡住的地方，就是这里，没有将前 \(cnt_0\) 个数和后 \(cnt_1\) 个数视为两部分，恒以为有交换和无交换是不同的，根本想不到上面。
所以做题不要死磕，实在不行就打暴力。
有效的交换为前 \(cnt_0\) 中的 \(1\) 与后 \(cnt_1\) 中的 \(0\) 进行交换，当 \(m=i\) 时，共 \(i^2\) 个，无效的为 \(C_n^2-i^2\)，令 \(dp_i\) 为 \(m=i\) 时的期望操作次数，\(dp_i=(\frac{i^2}{C_n^2}dp_{i-1}+\frac{C_n^2-i^2}{C_n^2}dp_i)+1\)，整理得 \(dp_i=dp_{i-1}+\frac{C_n^2}{i^2}\)。
易得 \(dp_0=0\)，通过数学归纳法得 \(dp_m=C_n^2\sum\limits_{i=1}^m\frac{1}{i^2}\)。
\(O(n)\) 求得逆元，后循环加起来做乘法即为答案。
代码如下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int MAXN=2e5+10,MOD=998244353;
int n,a[MAXN],cnt0,m,inv[MAXN],jc[MAXN],jcinv[MAXN];
namespace sol{
void solve(){
cnt0=m=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(!a[i])++cnt0;
}
for(int i=1;i<=cnt0;++i){
if(a[i])++m;
}
int ans=0;
for(int i=1;i<=m;++i){
ans=(1ll*ans+(1ll*inv[i]*inv[i]%MOD))%MOD;
}
ans=(1ll*ans*((1ll*n*(n-1)/2)%MOD))%MOD;
printf("%d\n",ans);
}
}
int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%MOD;
x=1ll*x*x%MOD;
y>>=1;
}
return ret;
}
int main(){
int T;scanf("%d",&T);
jc[0]=1;
for(int i=1;i<=(int)(2e5);++i){
jc[i]=1ll*jc[i-1]*i%MOD;
}
jcinv[(int)(2e5)]=qpow(jc[(int)(2e5)],MOD-2);
for(int i=(int)(2e5)-1;i;--i){
jcinv[i]=1ll*jcinv[i+1]*(i+1)%MOD;
}
for(int i=1;i<=(int)(2e5);++i){
inv[i]=1ll*jcinv[i]*jc[i-1]%MOD;
}
while(T--)sol::solve();
return 0;
}