yukicoder : No.2250 Split Permutation

これも割とすんなり。
https://yukicoder.me/problems/no/2250

問題

1～NのPermutation Pが与えられる。
Pをいくつかの部分列に分割し、各部分列をソート後、また連結することを考える。
分割の仕方は2^(N-1)通り考えられるが、それぞれこの処理後の転倒数の総和を求めよ。

解法

P[i]＞P[i+k]の場合、この2要素が処理後も転倒しているケースは、2^(N-1-k)通りである。
よって、P[i]の大きい順に処理することを考え、BITを使い区間における処理済みの要素数と、2^(N-1-i)の総和を取っておこう。

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

template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	V operator()(int e) { if(e<0) return 0; ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; v=(v%mo+mo)%mo; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<int,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;
	FOR(i,N) {
		cin>>P[i];
		R[N-P[i]]=i;
	}
	ll ret=0;
	FOR(i,N) {
		x=R[i];
		ret+=num(x)*modpow(2,N-1)%mo;
		ret-=bt(x)*modpow(2,N-1-x)%mo;
		bt.add(x,modpow(2,x));
		num.add(x,1);
	}
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

細かい数字を合わせるのに手間取った。