足跡-sokuseki-

りかの日進月歩の記録

ARC058 D いろはちゃんとマス目 / Iroha and a Grid

D - いろはちゃんとマス目 / Iroha and a Grid

問題概要

 H マス 横  W マスのグリッドの左上のマスから、右と下の移動を繰り返し右下のマスに移動する。
下から  A マス以内かつ左から  B マス以内のマスには移動できない。
移動する方法が何通りかを  10^9+7 で割った余りを求めよ。

制約
 2 \le H, W \le 10^5
 1 \le A < H
 1 \le B < W

解法

 x マス 横  y マスの長方形の移動は  _{x+y-2} C _{x-1} = \frac{ (x+y-2)! }{ (x-1)! (y-1)!} 通り。

階乗と階乗の逆元を  O(H+W) であらかじめ求めておく。

 0 \le i < H-A を満たす全ての  i について、  (0, 0), (i, B-1), (i, B), (H-1, W-1) を順に通る経路(つまり、 _{B+i-1} C_{B-1} \times  \  _{W-B-1 + H-i-1} C _{H-B-1} )の個数を数え上げて、総和を求めればよい。

Submission #2152295 - AtCoder Regular Contest 058