結果
問題 | No.660 家を通り過ぎないランダムウォーク問題 |
ユーザー |
![]() |
提出日時 | 2025-03-20 21:05:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 68,492 KB |
最終ジャッジ日時 | 2025-03-20 21:05:46 |
合計ジャッジ時間 | 3,320 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
MOD = 10**9 + 7 N = int(input()) max_fact = 2 * N - 1 if N == 0: print(0) exit() # Precompute factorial and inverse factorial arrays fact = [1] * (max_fact + 1) for i in range(1, max_fact + 1): fact[i] = fact[i-1] * i % MOD inv_fact = [1] * (max_fact + 1) inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD) for i in range(max_fact - 1, -1, -1): inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD def comb(n, k): if k < 0 or k > n: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD t_max = N // 2 result = 0 for t in range(t_max + 1): m = N + 2 * t if m > 2 * N: continue n = m - 1 k = t current = (comb(n, k) - comb(n, k - 1)) % MOD result = (result + current) % MOD print(result % MOD)