結果

問題 No.834 Random Walk Trip
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:24:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,561 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 75,728 KB
最終ジャッジ日時 2025-05-14 13:25:30
合計ジャッジ時間 2,861 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 10**9 + 7

# It's better to precompute factorials outside if multiple test cases,
# but for one test case, it can be inside main/solve.
# Max M is 10^6. Factorials up to M.
MAX_FACTORIAL_N = 10**6 + 5  # A bit of margin
fact = [1] * MAX_FACTORIAL_N
inv_fact = [1] * MAX_FACTORIAL_N

def precompute_factorials():
    for i in range(1, MAX_FACTORIAL_N):
        fact[i] = (fact[i - 1] * i) % MOD

    inv_fact[MAX_FACTORIAL_N - 1] = pow(fact[MAX_FACTORIAL_N - 1], MOD - 2, MOD)
    for i in range(MAX_FACTORIAL_N - 2, -1, -1): # From MAX_VAL-2 down to 0
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD

precompute_factorials() # Precompute once globally

def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    if n >= MAX_FACTORIAL_N: # Should not happen with M <= 10^6
        # Fallback or error, this indicates MAX_FACTORIAL_N is too small
        # For competitive programming, ensure MAX_FACTORIAL_N covers max possible n
        raise ValueError("n is too large for precomputed factorials")

    num = fact[n]
    den = (inv_fact[r] * inv_fact[n - r]) % MOD
    return (num * den) % MOD

def main():
    N, M = map(int, sys.stdin.readline().split())

    if N == 1:
        sys.stdout.write(str(1) + "\n")
        return

    if N == 2:
        # For M >= 1, dp[M][1] = 2^(M-1)
        ans = pow(2, M - 1, MOD)
        sys.stdout.write(str(ans) + "\n")
        return
    
    # Case N > 2: C(M, floor(M/2))
    k = M // 2
    ans = nCr_mod(M, k)
    sys.stdout.write(str(ans) + "\n")

if __name__ == '__main__':
    main()
0