提出 #67828372

---

ソースコード 拡げる

<?php

const MOD = 1000000007;
const MAX = 200000; // H + W の最大が 200000 まで対応可能

/**
 * @var array<int> $fact    階乗テーブル fact[n] = n! mod MOD
 * @var array<int> $invFact 逆元テーブル invFact[n] = (n!)^(-1) mod MOD
 */
$fact = array_fill(0, MAX + 1, 1);
$invFact = array_fill(0, MAX + 1, 1);

/**
 * 累乗を MOD で計算する（繰り返し二乗法）
 *
 * @param int $base 底
 * @param int $exp 指数
 * @return int base^exp % MOD
 */
function mod_pow(int $base, int $exp): int {
    $result = 1;
    $base %= MOD;

    while ($exp > 0) {
        if ($exp % 2 === 1) {
            $result = ($result * $base) % MOD;
        }
        $base = ($base * $base) % MOD;
        $exp = intdiv($exp, 2);
    }

    return $result;
}

/**
 * 階乗と逆元を事前計算
 *
 * @global array<int> $fact
 * @global array<int> $invFact
 * @return void
 */
function precompute_factorials(): void {
    global $fact, $invFact;

    for ($i = 1; $i <= MAX; $i++) {
        $fact[$i] = ($fact[$i - 1] * $i) % MOD;
    }

    $invFact[MAX] = mod_pow($fact[MAX], MOD - 2);
    for ($i = MAX - 1; $i >= 0; $i--) {
        $invFact[$i] = ($invFact[$i + 1] * ($i + 1)) % MOD;
    }
}

/**
 * nCr % MOD を返す
 *
 * @param int $n
 * @param int $r
 * @return int nCr mod MOD
 */
function combination(int $n, int $r): int {
    global $fact, $invFact;

    if ($r < 0 || $r > $n) {
        return 0;
    }

    return (int)((($fact[$n] * $invFact[$r]) % MOD) * $invFact[$n - $r] % MOD);
}

/**
 * 格子経路数を求める関数
 *
 * @param int $H 行数
 * @param int $W 列数
 * @return int 経路数（mod 1e9+7）
 */
function count_grid_paths(int $H, int $W): int {
    precompute_factorials();
    return combination($H + $W - 2, $H - 1);
}

/**
 * メイン処理：標準入力を読み取り、結果を出力
 */
function main(): void {
    [$H, $W] = array_map('intval', explode(' ', trim(fgets(STDIN))));
    echo count_grid_paths($H, $W) . PHP_EOL;
}

main();

提出情報

ジャッジ結果