题解：AT_arc154_e [ARC154E] Reverse and Inversion
int4399
·
·
题解
赛时唯一切这个题的人是通过做梦梦出来的。
记 $L_j=\sum\limits_{i<j}[p_i>p_j],R_i=\sum\limits_{i<j}[p_i>p_j]$，则 $f(p)=\sum\limits_{k=1}^n k (L_k-R_k)$。
考虑排列的特殊性，$k$ 左侧有 $k-1$ 个元素，其中有 $L_k$ 个比 $p_k$ 大，故有 $k-1-L_k$ 个比 $p_k$ 小，而右边有 $R_k$ 个比 $p_k$ 小，因此 $k-1-L_k+R_k=p_k-1$，即 $L_k-R_k=k-p_k$，因此 $f(p)=\sum\limits_{i=1}^n i(i-p_i)$。
我们不妨设 $e_i$ 表示 $p_i$ 经过操作后的期望位置，那么答案变为 $\sum\limits_{i=1}^n i^2-e_ip_i$，考虑怎么求 $e_i$。
当一个点 $i$ 被反转时，左端点的期望 $E(L)=\frac 1 i\sum\limits_{l=1}^i l=\frac{i+1} 2$，同理，$E(R)=\frac{i+n}{2}$。有趣的事情发生了，$E(R+L-i)=E(R)+E(L)-E(i)=\frac{i+1}2+\frac{i+n}{2}-i=\frac{n+1}{2}$。即只要 $i$ 经过反转，那么他的期望位置就是 $\frac{n+1}{2}$。
那么综合被选和不被选的情况考虑，$e_i=k_i^mi+(1-k_i^m)\frac{n+1}{2}$，其中 $k$ 表示 $i$ 不被选中的概率，$k_i=1-\frac{2i(n-i+1)}{n(n+1)}$。
然后算就可以了。
```
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
int qmi(int a,int b,int res=1){for(;b;b>>=1,a=1ll*a*a%P)if(b&1) res=1ll*res*a%P;return res;}
int n,m,p[N],e[N],ans;
int main(){
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>p[i];
int t=(-2ll*i*(n-i+1)%P*qmi(1ll*n*(n+1)%P,P-2)%P+P+1)%P;t=qmi(t,m);
e[i]=(1ll*i*t%P+1ll*(1-t+P)%P*(n+1)%P*qmi(2,P-2)%P)%P;
ans=(ans+1ll*i*i%P)%P,ans=(ans+P-1ll*e[i]*p[i]%P)%P;
}return cout<<1ll*ans*qmi(1ll*n*(n+1)/2%P,m)%P,0;
}
```