AtCoder ACL Contest 1 : E - Shuffle Window

こちらの方がいつものって感じだった。
https://atcoder.jp/contests/acl1/tasks/acl1_e

問題

1～Nの順列Pと、パラメータKが与えられる。
i回目の処理では、P[i]～P[i+K-1]をランダムにシャッフルする、ということを行う。
このような処理を計(P+1-K)回行う。
転倒数の期待値を求めよ。

解法

ある2つの数p＜qが最終的にどうなるかを考える。
一端両者が同時にランダムシャッフル対象に含まれる状態になったとき、転倒数が1増加する確率は1/2である。
また、シャッフル後のうち左端の1個の要素だけそれ以上シャッフルされない。

そこで、もしpがx回目、qがy回目の処理で初めてシャッフル対象となる場合、

• x≦yなら転倒数の期待値は*1/2
• y≦xなら転倒数の期待値は(((K-1)/K)^(y-x))/2

BITまたは範囲乗算可能なSegTreeを使い、数xがまだシャッフル対象に残っている確率を管理し、高速に配列全体に1/2を掛けたり、和を取れるようにしておこう。
端からシャッフル対象を徐々に加えながら、BITを更新していく。

int N,K;
int A[202020];

ll mo=998244353;
template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) {ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> bt,num;

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;
	FOR(i,N) cin>>A[i];
	
	ll r2=(mo+1)/2;
	ll ret=0;
	FOR(i,K) {
		bt.add(A[i],1);
		num.add(A[i],1);
	}
	
	ret=1LL*K*(K-1)%mo*r2%mo*r2%mo;
	
	ll p=(K-1)*modpow(K)%mo;
	ll rp=1;
	ll c=1;
	for(i=K;i<N;i++) {
		c=c*p%mo;
		// less
		(ret+=bt(A[i])*(c*r2%mo))%=mo;
		// more
		(ret+=(mo+bt(N)-bt(A[i]))*(mo-c*r2%mo))%=mo;
		(ret+=(mo+num(N)-num(A[i])))%=mo;
		bt.add(A[i],modpow(c));
		num.add(A[i],1);
	}
	
	cout<<ret<<endl;
	
}

まとめ

Codeforcesにありそう。

*1:1/K)^(y-x