ARC154E Reverse and Inversion 做题记录

给定 $n,m$ 和一个 $n$ 的排列 $P$。重复进行如下操作 $m$ 次：

• 选定 $1\le i\le j\le n$，并将 $P_i,P_{i+1},..,P_j$ 翻转。

对于所有 $(\frac{n(n+1)}{2})^m$ 种方案，计算 $\sum_{i<j}[P_i>P_j](j-i)$ 的值的和。

$1\le n,m\le 2\times 10^5$。

考虑拆开 $\sum_{i<j}[P_i>P_j](j-i)$：

$\begin{aligned} \sum_{i<j}[P_i>P_j](j-i)&=\sum\limits_{i}i\times \left(\sum\limits_{j<i}[P_i<P_j]-\sum\limits_{j>i}[P_i>P_j]\right)\\ &=\sum\limits_i i\times \left(i-\sum\limits_{j<i}[P_i\ge P_j]-\sum\limits_{j>i}[P_i>P_j]\right)\\ &=\sum\limits_i i\times \left(i-\sum\limits_{j}[P_i\ge P_j]\right)\\ &=\sum\limits_i i\times (i-P_i)\\ &=\sum\limits_i i^2-\sum\limits_i iP_i \end{aligned}$

那么只要求出 $\sum\limits_{i} iP_i$ 的和即可。

注意到操作只和位置相关，$P_i$ 的和不太好求，那么不妨转而求 $Q_i$ 表示 $P_i$ 最后去的位置（$P$ 的逆排列），那么 $\sum\limits_{i} iP_i=\sum\limits_{i} Q_iP_i$。

发现 $Q_i$ 还是不好求，这时候你突然灵光一闪就能想到，其实可以求 $S_i$ 表示 $Q_i$ 的期望，最后再乘上 $(\frac{n(n+1)}{2})^m$。

注意到 $S_i$ 是好求的。具体的，$P_i$ 一旦被某次操作覆盖到，那么它去往 $j$ 和去往 $n-j+1$ 的概率是一样的，因为你总能构建出双射。

那么答案即为 $(\frac{n(n+1)}{2})^m\left(\sum\limits_i i^2-\sum\limits_i S_iP_i\right)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005,p=998244353,inv2=(p+1)/2;

int n,m,a[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int calc(int n)
{
	return 1ll*(n+1)*n/2%p;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int sm=0;
	for(int i=1;i<=n;i++)
	{
		add(sm,1ll*i*i%p);
		int nc1=1ll*(calc(i-1)+calc(n-i))*qpow(calc(n),p-2)%p;
		int ncov=qpow(nc1,m);
		int si=0; 
		add(si,1ll*i*ncov%p);
		add(si,1ll*(n+1)*inv2%p*(p+1-ncov)%p);
		add(sm,p-1ll*si*a[i]%p);
	}
	sm=1ll*sm*qpow(calc(n),m)%p;
	printf("%d\n",sm);
	return 0;
}