AtCoder Beginner Contest 405, E : Fruit Lineup

問題文

　https://atcoder.jp/contests/abc405/tasks/abc405_e

問題概要

　$4$ 種の果物 $A, B, C, D$ がそれぞれ $a, b, c, d$ 個ずつある．これら $a + b + c + d$ 個の果物を以下の条件をすべて満たすように（左右）一列に並べる方法は何通りあるか？：

• すべての果物 $A$ について，それより左に果物 $C$ は無い．
• すべての果物 $A$ について，それより左に果物 $D$ は無い．
• すべての果物 $B$ について，それより左に果物 $D$ は無い．

　答えを $X$ として，$X \bmod 998244353$ を出力せよ．

制約

• $a, b, c, d \in [ 1, 10^6 ] \cap \mathbb Z$

解法

　理解のために果物の（ある種の）依存関係を図示すると以下のようになります：

　列を構成する問題で，空列から初めて要素を一種ずつ挿入していくことで解けるというのをしばしば見る気がするので，そのような方向性で考えてみます．本問の場合は，$2$ 種を取り出して並べる方法が一意に定まるような組が $3$ つ与えられているので，空列ではなくこれらの内いずれかから考え始めることができます．最初にどれを固定するかは SNS などを見ていると色々ある気がしますが，ここでは $B, D$ だけを並べた状態から $A, C$ の順に挿入していくことにします．
　$B, D$ のみを並べる方法は，連続する $b$ 個の $B$ に続いて連続する $d$ 個の $D$ を並べるしかないので並べ方は $1$ 通りです．ここへ，$a$ 個の $A$ をまとめて挿入してから $c$ 個の $C$ をまとめて挿入しますが，$C$ を挿入できる位置は最も右にある $A$ の位置に依存します．なので，最も右にある $A$ の位置を全通り試して並べ方の数の和をとることで答えを求めます．
　$A$ を挿入できる位置は最も左にある $B$ の左隣から最も右にある $B$ の右隣までの $b + 1$ 箇所で，最も右にある $A$ より左にある $B$ の個数を $i$ とすれば $0 \leq i \leq b$ の範囲で調べる必要があります．$i$ を固定したとき，$i$ 番目の $B$ の右（$i = 0$ のときは $1$ 番目の $B$ の左）には少なくとも $1$ つの $A$ がなければなりません．よって，残り $a - 1$ 個の $A$ を $i$ 個の $B$ が並んだ列に挿入することになります．先頭・末尾を含めると挿入できる箇所（口語的には $B$ と $B$ の"間"）は $i + 1$ 箇所あります．よってやりたいことは，$i + 1$ 個の箱に $a + 1$ 個の $A$ を振り分ける方法の総数を求めることであると言い換えられます．更に言い換えると，$i + 1$ 個の箱から $a + 1$ 個を重複を許して選ぶ方法の総数です．$n$ 種のものから重複を許して $k$ 個選び取る方法の総数は重複組合せとして知られ，
\[
\binom { n + k - 1 } k
\]
という二項係数と一致します．従って，求めたかった $i + 1$ 箇所に $a + 1$ 個を挿入する方法の総数は
\[
\binom { a - 1 + i } { a - 1 }
\]
通りとなります．
　$D$ を挿入する方法も同様にして考えます．最も右の $A$ より右に $D$ を挿入しなければならなかったわけですが，最も右の $A$ は $i$ 番目の $B$ の右に挿入したので，残っている $B, D$ の数を考えると $D$ を挿入できる位置は $b + d - i + 1$ 箇所です．よって，$D$ を挿入する方法の総数は
\[
\binom { c + b + d - i } c
\]
通りとなります．
　以上をまとめれば，出力するべき値は
\[
\sum_{ i = 0 }^b \binom { a - 1 + i } { a - 1 } \binom { c + b + d - i } c \bmod 998244353
\]
です．
　上記の値は二項係数を $\Theta( b )$ 回計算することで求められます．必要な範囲での階乗の値を前計算するなどすることで，TL に間に合わせることができます．具体的な計算方法については問題固有の話題から逸れるので割愛しますが，蟻本 [1] などに記載があります．

参考文献

[1] 秋葉拓哉; 岩田陽一; 北川宜稔. プログラミングコンテストチャレンジブック ~ 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~. マイナビ出版, 2012.

コード

constexpr int MOD = 998244353;

#include <atcoder/modint>
using namespace atcoder;
using MINT = modint998244353;
inline ostream& operator<<( ostream &s, const MINT &t ){ s << t.val(); return s; }

// a^x を mod で求める
// 反復二乗法
// O( log x )
long long mod_pow( long long a, long long x, long long mod );
// 中身省略

// p が素数のとき、p を法とする剰余体での逆元を求める
// Fermat の小定理を利用
// a^{ p - 1 } \equiv 1 ( mod p )
// a^{ p - 2 } \equiv a^{-1} ( mod p )
int mod_inverse( long long a, long long p );
// 中身省略

// 素数を法とする剰余体での n! を求める
class modFact;
// 中身省略
// modfact( max_n, mod )
// ()( n )
// ()( n, e )

// nCr
// include : modFact, mod_inverse
class modComb;
// 中身省略
// modComb( n, mod )
// ()( n, r )
modComb nCr( 4'000'000, MOD );

int main()
{
	IN( int, A, B, C, D );

	MINT res = 0;
	REP( i, B + 1 )
	{
		res += MINT( nCr( A - 1 + i, A - 1 ) ) * nCr( C + ( B + D ) - i, C );
	}
	cout << res << endl;

	return 0;
}