提出 #67828205

---

ソースコード 拡げる

import sys
from typing import List

MOD: int = 10**9 + 7
MAX: int = 200000  # H+Wの最大を考慮して十分大きい上限

fact: List[int] = [1] * (MAX + 1)       # fact[i] = i!
inv_fact: List[int] = [1] * (MAX + 1)   # inv_fact[i] = (i!)^(-1) mod MOD


def modinv(a: int) -> int:
    """
    a^(-1) mod MOD を求める（フェルマーの小定理を使用）
    @param a: 逆元を求める数（a ≠ 0）
    @return: a の MOD における逆元
    """
    return pow(a, MOD - 2, MOD)


def precompute_factorials() -> None:
    """
    階乗とその逆元を事前計算して、fact[], inv_fact[] に格納する
    """
    for i in range(1, MAX + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact[MAX] = modinv(fact[MAX])
    for i in range(MAX - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD


def comb(n: int, r: int) -> int:
    """
    nCr (mod MOD) を返す
    @param n: 総数（0 <= r <= n <= MAX）
    @param r: 選ぶ数
    @return: nCr % MOD
    """
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD


def count_grid_paths(H: int, W: int) -> int:
    """
    格子経路数を計算：C(H+W-2, H-1)
    @param H: 行数
    @param W: 列数
    @return: 経路数（mod 1e9+7）
    """
    precompute_factorials()
    return comb(H + W - 2, H - 1)


def main() -> None:
    """
    標準入力を読み取り、格子経路数を出力する
    """
    H_str, W_str = sys.stdin.read().split()
    H: int = int(H_str)
    W: int = int(W_str)
    result: int = count_grid_paths(H, W)
    print(result)


if __name__ == "__main__":
    main()

提出情報

ジャッジ結果