AtCoder ABC #380 : G - Another Shuffle Window

まぁこれはすんなり。
https://atcoder.jp/contests/abc380/tasks/abc380_g

問題

1～Nの順列Pと、整数Kが与えられる。
Pのうち連続するK要素を選び、ランダムにシャッフルするとき、その後の転倒数の期待値を求めよ。

解法

長さKの整数列をランダムにシャッフルしたとき、転倒数はK*(K-1)/4となる。
f(i) := P[i...(i+K-1)]の転倒数
とすると、解はPの転倒数からf(i)の平均値を引き、K*(K-1)/4を足したものになる。
あとはf(i)の平均値を求めればよいが、これは尺取り法の要領でf(0),f(1),....f(N-1-K)を求めればよい。

int N,K;
int P[202020];
const ll mo=998244353;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

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>>K;
	ll base=0;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		base+=bt(N)-bt(P[i]);
		bt.add(P[i],1);
	}
	
	FOR(i,N) bt.add(i,-1);
	
	ll add=0;
	ll cur=0;
	FOR(i,K-1) {
		(cur+=bt(N)-bt(P[i])+mo)%=mo;
		bt.add(P[i],1);
	}
	for(i=K-1;i<N;i++) {
		(cur+=bt(N)-bt(P[i])+mo)%=mo;
		(add+=cur)%=mo;
		bt.add(P[i],1);
		(cur+=mo-bt(P[i-(K-1)]-1))%=mo;
		bt.add(P[i-(K-1)],-1);
	}
	add=add*modpow(N+1-K)%mo;
	base=base+mo-add+1LL*K*(K-1)%mo*modpow(4)%mo;
	cout<<base%mo<<endl;
	
	
}

まとめ

650ptとか575ptとか、G問題は難易度のブレ幅大きいな…。