White and Black Balls [AtCoder Beginner Contest 205 E]

https://atcoder.jp/contests/abc205/tasks/abc205_e

前提知識

• カタラン数

解説

https://atcoder.jp/contests/abc205/submissions/23454802

この問題は類題を知っていれば解法は一瞬で思いつくが、知らないと一生解けない（少なくとも自分は…）
この問題はカタラン数とかdyck列とかカッコ列対応問題とかそういった類の問題となる。

カタラン数

類題を色々以下に置いてあるが、とりあえずAOJの１０歳の動的計画が入門問題となるので、今回の問題に取り組む前にこちらを理解することをお勧めする。
競技プログラミングにおける数学的問題まとめ - はまやんはまやんはまやん
カタラン数とかでググると解説も多く見つかるだろうのでこの部分は理解しているとして話を進める。
（正直、ここの理解がこの問題で一番キツい所）

カタラン数を適用する

今回の問題はカタラン数での捉え方と同様に格子上の経路数え上げに帰着することができる。
縦に使った白の個数、横に使った黒の個数を軸に取ると、とある格子上の経路がボールの並べ方に対応する。
ここで重要なのが、wi≦bi+Kにおいて、K=0の場合を考えると、カタラン数の場合の数え上げと同じ状況になっていることである。
よってK=0の場合は、カタラン数での数え上げ方と同様にC(N+M,N)-C(N+M,N-1)で計算ができる。
そうでない、例えばK=1の場合もそれほど難しくなく、格子状の直線の切片が1だけ上に上がるだけなので、C(N+M,N)-C(N+M,N-2)とすればいい。
よって、基本的にはC(N+M,N)-C(N+M,N-K-1)が答えになる。

コーナーケース1

この問題では追加でコーナーケースを考える必要がある。
立式を見るとN=Kの時にN-K-1が-1になるのでどうなんだろうという感じになる。
N=Kの時はどんなふうに選択してもOKなので、C(N+M,N)が答え。
この辺は二項係数が-1の時は0を返す仕様（というか本来そうか？あまりちゃんと考えてない）ならまとめられる。

コーナーケース2

並べ方が存在しない場合に計算がおかしくなるので、存在しない場合は場合分けをして0を答えよう。
そうなる条件は N ＞ M+Kである。
全部置き切ったときに条件が満たせてないなら、実現不可能である。

int N, M, K;
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    mint ans;
    if (N > M + K) ans = 0;
    else if (N == K) ans = com.aCb(N + M, N);
    else ans = com.aCb(N + M, N) - com.aCb(N + M, N - K - 1);
    cout << ans << endl;
}