Matsushita's Blog

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題

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)に変換可能)

の経路数を数え上げる。

ソースコード