但愿我学过排序 题解

思路

设数组中有 $z$ 个零。有序数组的前 $z$ 位都应为零。令 $x$ 为当前前 $z$ 位中的一的个数，则后半部分恰有 $x$ 个零。只有选中“前半部分的一”和“后半部分的零”时，$x$ 才会减少 $1$，这样的下标对恰有 $x^2$ 个。

总下标对数为 $C=\binom n2$。从状态 $x$ 等到一次有效交换的期望操作数为 $C/x^2$，所以

三个层级为：小规模枚举全部二进制状态并解马尔可夫线性方程；中等规模使用上述一维递推并逐项快速幂求逆；满规模线性预处理所有逆元平方的前缀和。

做法

预处理 $inv[i]=i^{-1}\pmod{998244353}$，再令

每组统计零的总数 $z$ 以及前 $z$ 位中的一的个数 $x$，答案就是

数组已经有序时 $x=0$，答案自然为零。

复杂度

逆元与前缀和预处理为 $O(N)$，每组扫描数组为 $O(n)$；总时间 $O(N+\sum n)$，空间 $O(N)$。