[ARC154E] Reverse and Inversion 题解

题目链接

点击打开链接

题目解法

\(\sum j-i\) 是不好维护的，考虑把 \(j-i\) 拆成之和 \(i,j\) 相关的项
可以得到：\(\sum\limits_{i<j}[p_i>p_j](j-i)=\sum\limits_{i=1}^n i(\sum\limits_{j=1}^{i-1}[p_j>p_i]-\sum\limits_{j=i+1}^n[p_j<p_i])=\sum\limits_{i=1}^ni(i-1-\sum\limits_{j=1}^n[p_j<p_i])=i(i-p_i)\)
前面的 \(i^2\) 是好弄的，考虑如何求所有情况的 \(\sum ip_i\)
从概率方面考虑这个问题，从位置 \(i\) 翻转到位置 \(j\) 的方案数为 \(\min\{i,n-i+1,j,n-j+1\}\)，从而可见 \(i\) 翻转到位置 \(j\) 和位置 \(n-j+1\) 的概率是一样的，所以位置 \(i\) 的数只要翻转过，期望移到的位置都为 \(\frac{n+1}{2}\)
每个位置没有翻转到的概率是好求的，令其为 \(gl_i\)，所以答案即为 \((\frac{n(n+1)}{2})^m(\sum i^2-\sum( gl_i\times ip_i+(1-gl_i)\times \frac{n+1}{2}p_i))\)

时间复杂度 \(O(n\log P)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=200100,P=998244353;
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
    return res;
}
int n,m,p[N];
int main(){
    n=read(),m=read();
    F(i,1,n) p[i]=read();
    int iv2=qmi(2,P-2);
    int tot=qmi((1ll*n*(n+1)/2)%P,m),iv=qmi(tot,P-2);
    int ans=0;
    F(i,1,n) ans=(ans+1ll*i*i)%P;
    int t=1ll*(n+1)*iv2%P,res=0;
    F(i,1,n){
        int ways=(1ll*i*(i-1)+1ll*(n-i)*(n-i+1))%P*iv2%P;
        int gl=1ll*qmi(ways,m)*iv%P;
        res=(res+1ll*gl*p[i]%P*i+1ll*(P+1-gl)*t%P*p[i])%P;
    }
    ans=(ans-res+P)%P;ans=1ll*ans*tot%P;
    printf("%d\n",ans);
    return 0;
}