ARC058 D いろはちゃんとマス目 / Iroha and a Grid
D - いろはちゃんとマス目 / Iroha and a Grid
問題概要
縦 マス 横 マスのグリッドの左上のマスから、右と下の移動を繰り返し右下のマスに移動する。
下から マス以内かつ左から マス以内のマスには移動できない。
移動する方法が何通りかを で割った余りを求めよ。
制約
解法
縦 マス 横 マスの長方形の移動は 通り。
階乗と階乗の逆元を であらかじめ求めておく。
を満たす全ての について、 を順に通る経路(つまり、)の個数を数え上げて、総和を求めればよい。