yukicoder : No.1989 Pairing Multiset

シンプルな解。
https://yukicoder.me/problems/no/1989

問題

整数N,Mが与えられる。
0～Mの範囲の2N要素の多重集合Sを考える。
f(S)を、Sの要素を2つずつ組にしてN組作り、それぞれの組の値の差の絶対値の総和の最小値とする。

あり得るSすべてにおけるf(S)の総和を求めよ。

解法

Sに対し、昇順に2つずつ組にすれば明らかに最小。
f(S)を以下のように表現する。
(0,0)-(2N,M)で構成されるグリッドにおいて、(0,0)から(2N,M)に向かう経路を考える。
経路全パターンにおいて、x座標が奇数の位置でy座標を増加させた回数の総和がf(S)となる。

1つのx座標で考えると、各y座標を増加させるような移動経路を含む経路の総和はC(2N+M,2N+1)となる。
x座標が奇数となるのはN箇所あるので、N倍すれば解。

ll N,M;
const ll mo=998244353;

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

ll comb(ll P_,ll Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=N*comb(2*N+M,2*N+1)%mo;
	cout<<ret<<endl;
	
}

まとめ

この二項係数の言い換え方は覚えておきたい。