yukicoder : No.2616 中央番目の中央値

これは割とすんなりだった。
https://yukicoder.me/problems/no/2616

問題

Pの順列が与えられる。
Pの奇数長の部分列のうち、真ん中の要素が中央値であるのは何通りか。

解法

中央値を総当たりする。
P[x]が中央値となるケースを考える。

• a: xの左側にあるP[x]より小さい値の個数を選ぶ数
• b: xの左側にあるP[x]より大きい値の個数を選ぶ数
• c: xの右側にあるP[x]より小さい値の個数を選ぶ数
• d: xの右側にあるP[x]より大きい値の個数を選ぶ数

とすると、

• 中央値の条件よりa+c=b+d
• 真ん中の条件よりa+b=c+d

両式より、a=d、b=cとなるような選び方を考える。

• A: xの左側にあるP[x]より小さい値の個数
• B: xの左側にあるP[x]より大きい値の個数
• C: xの右側にあるP[x]より小さい値の個数
• D: xの右側にあるP[x]より大きい値の個数

とすると、a=dとなるようなa+d要素の選び方はBinom(A+D,A)となる。
これはA個の中からa個を選びつつ、D個の中から(A-a)個を選ぶのは、結局(A+D)個からA個選ぶのと同じためである。
同様にb=cとなるようなa+d要素の選び方はBinom(B+C,B)となる。

int N;
int P[302020];

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<int,20> bt;

const ll mo=998244353;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		int LS=bt(x);
		int LL=i-LS;
		int RS=x-1-LS;
		int RL=N-1-LS-LL-RS;
		
		(ret+=comb(LS+RL,LS)*comb(LL+RS,LL))%=mo;
		
		bt.add(x,1);
	}
	cout<<ret<<endl;
	
	
}

まとめ

★3っぽいお手頃な問題。