题解 - ZR 2925 逆序对(inversion)

非常好 Bijection Proof。

简述题意

诶我可以放题意的吗？那我们只知道 $1\le n,m\le 5\times 10^5$。

分析

那先把期望改逆序对和，反正方案数已经写在题面上了。

莫名其妙的对称性

先不考虑 $l+r=n+1$ 的操作，假设有 $l=1\lor r=n$ 的操作，那么把这一步替换为 $(n-r+1,n-l+1,1-t)$ 后，整个序列翻转。把这以后的操作都变为 $(n-r+1,n-l+1,t)$，最后的序列也刚好相反。所以这样子的操作序列可以构成双射，期望逆序对数目 $\frac{n(n-1)}{4}$。你要说怎么观察到的，我还真不知道，感觉还挺困难。

假设没有 $l=1\lor r=n$ 的操作，令 $d=\min(l-1,n-r)$，那么 $a_1\sim a_{d-1}$ 和 $a_{n-d+1}\sim a_n$ 都保持不变，也就是说它们参与的逆序对不会发生改变。令这样的逆序对总数为 $c_d$，则此时期望的逆序对数目为 $\frac{(n-2d){n-rd-1}}{4}+c_d$。

莫名其妙的构造

然后我们要考虑 $l+r=n+1$ 的操作。我们还是希望某种办法能让它的期望逆序对数目还长那样，要不然直接容斥做这个 reverse 太难了。所以要有一种操作和它对偶。

令 $(1,n,0)$ 和 $(1,n,-1)$ 双射，$(1,n,1)$ 和 $(1,n,-2)$ 双射，这两个 $t<0$ 的操作什么都不用做，所以成功对偶，只是它是不合法的。你要说怎么想到的，我还是不知道，感觉非常困难。

终于可以开始数数了

二项式反演容斥掉 $t<0$ 的操作。总逆序对数：

$$\sum_{i=0}^m (-1)^{m-i}\binom{m}{i}(2\lceil\frac{n}{2}\rceil)^{m-i} \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}(t_j^i-t_{j+1}^i)(c_j+\frac{(n-2j)(n-2j-1)}{4})$$

我们假装 $i=0$ 的时候它可以正常运作，但是你要问我为什么，我还是不知道，它就这么过的。

把 $j$ 提出来：

$$\begin{aligned}&v_j\sum_{i=0}^m (-1)^{m-i}\binom{m}{i}(2\lceil\frac{n}{2}\rceil)^{m-i}t_j^i\\ =& v_j(t_j-2\lceil\frac{n}{2}\rceil)^m\end{aligned}$$

其中 $v$ 是某一个可以被计算的系数。

然后就可以了。计算 $v$ 要树状数组，计算答案要快速幂，复杂度 $O(n\log n)$。

代码

const int MXN = 500005;
const int DVS = 998244353;
const int INV2 = 499122177;
int N, M, perm[MXN], ans, sum[MXN], coe[MXN];

inline int query(int x) {
  int v(0);
  while (x) v += sum[x], x -= x & -x;
  return v;
}
inline void add(int x) {
  while (x <= N) ++sum[x], x += x & -x;
}

int pw(int b, int p) {
  int a(1);
  while (p) {
    if (p & 1) a = a * 1LL * b % DVS;
    b = b * 1LL * b % DVS;
    p >>= 1;
  }
  return a;
}
void exgcd(int a, int b, int& x, int& y) {
  if (!b) x = 1;
  else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int getinv(int a) {
  int x(0), y(0);
  exgcd(a, DVS, x, y);
  return (x % DVS + DVS) % DVS;
}

int main() {
  scanf("%d%d", &N, &M);
  for (int i(0); i != N; ++i) scanf("%d", &perm[i]);
  if (N & 1) add(perm[N >> 1]);
  for (int i(N / 2); i; --i) {
    coe[i] += query(perm[i - 1]);
    add(perm[i - 1]);
    if (N - i != i - 1) {
      coe[i] += N - i - i + 1 - query(perm[N - i]);
      add(perm[N - i]);
    }
  }
  for (int i(1); i <= N / 2; ++i)
    coe[i] = (coe[i] + coe[i - 1]) % DVS;
  for (int i(0); i <= N / 2; ++i)
    coe[i] = (coe[i] + (N - i - i) * 1LL * (N - i - i - 1) / 2 % DVS * INV2) % DVS;
  for (int i(N / 2 - 1); ~i; --i)
    coe[i + 1] = (coe[i + 1] - coe[i] + DVS) % DVS;
  for (int i(0); i <= N / 2; ++i) {
    int b(((N - i - i) * 1LL * (N - i - i + 1) + (N - i - i + 1) / 2 * 2) % DVS);
    b = (b + DVS - (N + 1) / 2 * 2) % DVS;
    ans = (ans + coe[i] * 1LL * pw(b, M)) % DVS;
  }
  ans = ans * 1LL * getinv(pw(N * 1LL * (N + 1) % DVS, M)) % DVS;
  printf("%d\n", ans);
  return 0;
}