yukicoder : No.2033 Chromatic Duel

これは★3.5位でもいいかも。
https://yukicoder.me/problems/no/2033

問題

N個のマスが並んでいる。
先手がうちB個のマスを黒く塗ったとする。この組み合わせはBinom(N,C)通りある。
この時、後手は空きマスのうち、黒マスに隣接しないマスを白く塗ったとする。
この場合白マスの最大数がWとなるような、黒マスの塗り方は何通りか。

解法

黒マス間に2マス以上の空きマスがある場合、(空きマス数-2)個の白マスを間に塗ることができる。
加えて、最初の黒マスの前と最後の黒マスの後は、(空きマス数-1)個の白マスを間に塗ることができる。

そこで、

• 最初の黒マスの前に空きマスがあるかどうか
• 最後の黒マスの後に空きマスがあるかどうか
• 黒マス間のうち、2マス以上の空きマスがある箇所は何通りか

をそれぞれ総当たりしよう。
「黒マス間のうち、0マス/1マスの空きマスがある箇所」は、BとWの値から1マスの空きマスの個数がわかるので二項係数で計算できる。
また、白マスを空きマス間にどう入れるかは重複組み合わせの要領で計算できる。

int N,B,W,S;
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;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B>>W;
	S=N-B-W;
	
	ll ret=0;
	FOR(i,B) {
		ll a=comb(B-1,i);
		{//両端空きマスあり
			int s=S-2*i-2;
			ll b=comb(B-1-i,s);
			ll c=hcomb(i+2,W);
			ret+=a*b%mo*c%mo;
		}
		{//片側空きマスあり
			int s=S-2*i-1;
			ll b=comb(B-1-i,s);
			ll c=hcomb(i+1,W);
			ret+=2*a*b%mo*c%mo;
		}
		{//両方空きマスなし
			int s=S-2*i;
			ll b=comb(B-1-i,s);
			ll c=hcomb(i,W);
			ret+=a*b%mo*c%mo;
		}
	}
	cout<<ret%mo<<endl;
	
	
	
}

まとめ

これは割とすんなり。