【學習筆記】[ARC154E] Reverse and Inversion

學好數學

首先對于位置 i i i，設 g ( i ) = ∑ j < i [ Q j > Q i ] − ∑ j > i [ Q j < Q i ] g(i)=\sum_{j<i}[Q_j>Q_i]-\sum_{j>i}[Q_j<Q_i] g(i)=∑j<i​[Qj​>Qi​]−∑j>i​[Qj​<Qi​]，有結論 g ( i ) = i − Q i g(i)=i-Q_i g(i)=i−Qi​。

道理很簡單， g ( i ) = i − ∑ j ≤ i [ Q j ≤ Q i ] − ∑ j > i [ Q j ≤ Q i ] = i − Q i g(i)=i-\sum_{j\le i}[Q_j\le Q_i]-\sum_{j>i}[Q_j\le Q_i]=i-Q_i g(i)=i−∑j≤i​[Qj​≤Qi​]−∑j>i​[Qj​≤Qi​]=i−Qi​

那麼我們隻要算 i i i的期望位置就好了。顯然如果 i ∉ [ l , r ] i\notin [l,r] i∈/[l,r]那麼這次操作對 i i i沒有影響，那麼我們隻要算出 i ∈ [ l , r ] i\in [l,r] i∈[l,r]時對應位置的期望即可。不難暴力算出此時 i i i的期望位置是 n + 1 2 \frac{n+1}{2} 2n+1​，是以隻要 i i i被操作了一次那麼位置就是 n + 1 2 \frac{n+1}{2} 2n+1​，否則就是原位置。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int mod=998244353;
int n,m,Q[200005];
ll f[200005],res;
ll pw(ll x,ll y=mod-2){
	x%=mod;ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;for(int i=1;i<=n;i++)cin>>Q[i],res=(res+(ll)i*i)%mod;
    ll X=pw((ll)n*(n+1)/2%mod);
    for(int i=1;i<=n;i++){
    	ll Y=X*i%mod*(n-i+1)%mod;
    	res=(res-pw(1-Y,m)*i%mod*Q[i]%mod)%mod;
    	res=(res-(1-pw(1-Y,m))*(n+1)%mod*pw(2)%mod*Q[i]%mod)%mod;
	}res=res*pw((ll)n*(n+1)/2,m)%mod;
	cout<<(res+mod)%mod;
}