フェルマーの小定理による組み合わせ計算によって経路数を数え上げる
問題
D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder
解法
まず、この問題のポイントを抑える
問題のポイント
- 右と下にのみ移動可能なマス目の経路数の数え上げ
- 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105)
- ABによって作成される四角形内は進入不可
それぞれ見ていく
右と下にのみ移動可能なマス目の経路数の数え上げ
これは、座標(0, 0)から(x, y)までに行く経路数はx+yCx(x+y個の中からx個選ぶ組み合わせ)で求める事ができる。よって今回の問題は組み合わせを求める問題に変換できる。
縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105)
nCkはn! / (k! * (n-k)!)で表す事ができるが、今回はn = H + Wとなりとても大きい数値となる。この時nCkはかなり大きい数字であり保持できずINFに飛んでしまう。それを考慮して問題ではnCkを109+7(素数)で割った余りを出力するように指定されている。
そこで、nCk = n! / (k! * (n-k)!)を計算する過程でmod(109+7)を行うことで計算中に値がINFにならないようにする。
これをするためにフェルマーの小定理を用いる。
フェルマーの小定理によるコンビネーションの計算は以下を参照。
keita-matsushita.hatenablog.com
フェルマーの定理によってnまでの階乗と逆元を用意する(計算量O(log(n!))。これによってO(1)でnCkを計算することができる。 階乗と逆元を用意することを含めて nCkを計算量 O(log(N!))で求める事ができる。これはO(NlogN)より小さい。
ABによって作成される四角形内は進入不可
最後にこの制約によってB <= i < Wにおけるすべてのiに対して
(0, 0) → (H - A - 1, i)
(H - A, i) → (H - 1, W - 1) (=> (0, 0) → (A - 1, W - i - 1)に変換可能)
の経路数を数え上げる。
