FHC round1 25. Winning at Sports

その他

問題

試合結果「A-B」が与えられ、Aは自分の点数、Bは相手の点数になっている。
今、2つの試合運びを考える。
「stress-free」な試合運びとは、最初に1-0になって、そのあとは、A-Bになるまで常に相手に点数が勝ち続けた状態で試合が進むことをいう。
「stressful」な試合運びとは、最初からB-Bになるまで相手の点数を超えない点数で試合が進み、B-BからA-Bまで連続で点数が入るような試合の進み方をいう。
2つの試合運びについて、そのような点数の変化の仕方が何通りあるかMOD 10^9+7で求める。


A,Bは非負で2000を超えない

考え方

2次元グリッドを考え、縦方向を自分の点数、横方向を相手の点数とし、原点から条件を満たしつつ、右か上のみ移動し、それぞれ(B,A)、(B,B)にたどり着くルートの数、と考えられる。


これは、経路の組み合わせなので、dp[i][j]:=自分の点数がi＆相手の点数がjとなるルート総数、として基本的にdp[i][j]=dp[i-1][j]+dp[i][j-1]で求められる。


ちなみに、stressfulな進め方は、カタラン数になっている。