ABC 034 C - 経路 - ペンギンかっこいい

備忘録

問題

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def factorial_mod(N, MOD):
    ret = 1
    for n in range(1, N + 1):
        ret *= n
        ret %= MOD
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    W, H = il()
    n = factorial_mod(W + H - 2, MOD)
    b = factorial_mod(H-1, MOD)
    d = factorial_mod(W-1, MOD)
    b = pow(b, MOD-2, MOD)
    d = pow(d, MOD - 2, MOD)
    print((n*b*d)%MOD)


if __name__ == '__main__':
    main()

考え方

経路の組み合わせを求める問題。

【数学の最短経路問題】解き方のコツ・公式｜スタディサプリ大学受験講座

普通に行うと階乗の計算で数値が大きくなりすぎてしまう。
そのため、下記を参考に、階乗の処理中にMOD(10e9+7)の余りをもとめ、
フェルマーの小定理により処理を高速化している。

フェルマーの小定理の証明と例題 | 高校数学の美しい物語

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita

フェルマーの小定理を用いたCombination(組み合わせ)計算 - Qiita

フェルマーの小定理についてはまだちゃんと理解できておらず、
雰囲気実装なので今後勉強が必要。。

素数の余りを求める問題ではフェルマーの小定理を利用することで、
高速に計算することができるが、
実はpythonなら何も特別なことをしなくても解ける。。。

    # 上記の回答例は実行時間 80ms秒でACできるが、
    # 以下のような実装でも実行時間が1600ms秒ほどになるが、一応ACする
    W, H = il()
    n = math.factorial(W+H-2)
    d = (math.factorial(W-1) * math.factorial(H-1) )
    print((n//d)%MOD)