AtCoder ARC #154 : E - Reverse and Inversion

意外にコードは短い。
https://atcoder.jp/contests/arc154/tasks/arc154_e

問題

1～Nの順列Qに対し、f(Q)を以下のように定める。

• i＜jかつQ[i]＞Q[j]である(i,j)に対するj-iの総和

今1～Nの順列Pが与えられる。
ここから区間をランダムに選択し、反転することをM回繰り返す。
区間の選び方は(N*(N+1)/2)通りあるので、(N*(N+1)/2)^M全通りにおける処理終了後のf(P)の総和を求めよ。

解法

f(P)は式変形すると、となる。
また、1回でも反転に巻き込まれた要素は、最終的な位置の頻度分布は左右対称になるので、P_iは平均値を考えればよい。
よって、各要素に対し1回も反転に巻き込まれないケースを数え上げれ行けばよい。

int N,M;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=0;
	for(i=1;i<=N;i++) {
		ll allpat=modpow(1LL*N*(N+1)/2,M);
		ret+=1LL*i*i%mo*allpat%mo;
	}
	
	ll p2=(mo+1)/2;
	for(i=1;i<=N;i++) {
		int P;
		cin>>P;
		//iを巻き込まない確率
		ll move=(1LL*i*(N+1-i))%mo;
		ll stay=(1LL*N*(N+1)/2-move+mo)%mo;
		ll allstay=modpow(stay,M);
		ll onemove=(modpow(1LL*N*(N+1)/2,M)-allstay)%mo;
		ret+=allstay*i%mo*(mo-P)%mo;
		ret+=onemove*(N+1)%mo*p2%mo*(mo-P)%mo;
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

式変形も、左右対称になることも、言われればシンプルなんだけど本番中に思いつけないんだよな。