526互联

Atcoder Regular Contest 154 E - Reverse and Inversion

发布时间 2023-07-21 17:48:36作者: tzc_wk

只要你发现是诈骗题就好办了。不要像我那样傻傻地瞪一个小时然后才发现那俩 sigma 里的东西相减是有性质的。

先考虑计算单个 \(f(p)\)，一眼的树状数组……吗？考虑最终答案式子里 \(i\) 的系数：\(\sum\limits_{j<i}[p_j>p_i]-\sum\limits_{j>i}[p_j<p_i]\)，因为 \(\sum\limits_{j<i}[p_j>p_i]+\sum\limits_{j<i}[p_j<p_i]=i-1\)，\(\sum\limits_{j<i}[p_j<p_i]+\sum\limits_{j>i}[p_j<p_i]=p_i-1\)，所以两者相减可以得到 \(\sum\limits_{j<i}[p_j>p_i]-\sum\limits_{j>i}[p_j<p_i]=i-p_i\)。于是 \(f(p)=\sum\limits_{i=1}^n(i^2-ip_i)\)。

\(\sum i^2\) 是定值。考虑计算 \(E(\sum ip_i)\)。发现一个很重要的性质：对于一个当前在位置 \(i\) 的数，只要下一次操作区间包含 \(i\)，那么 \(\forall j\)，下一步操作到达 \(j\) 的概率和到达 \(n-j+1\) 的概率是完全相同的。也就是说考虑一个位置 \(i\) 上的数 \(p_i\)，如果其被操作至少一次，那么最终 \(p_i\) 所在位置的期望值就是 \(\dfrac{n+1}{2}\)，因此最终 \(p_i\) 位置的期望值可以容易算出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5;
const int MOD=998244353;
const int INV2=MOD+1>>1;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,m,p[MAXN+5],res;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++){
		int p0=1ll*(1ll*i*(i-1)/2+1ll*(n-i)*(n-i+1)/2)%MOD*qpow(1ll*n*(n+1)/2%MOD,MOD-2)%MOD;
		res=(res+1ll*i*i)%MOD;
		res=(res-(1ll*qpow(p0,m)*p[i]%MOD*i+1ll*(1-qpow(p0,m)+MOD)*p[i]%MOD*(n+1)%MOD*INV2)%MOD+MOD)%MOD;
	}printf("%d\n",1ll*res*qpow(1ll*n*(n+1)/2%MOD,m)%MOD);
	return 0;
}