結果
問題 | No.834 Random Walk Trip |
ユーザー | 37zigen |
提出日時 | 2019-05-25 01:00:50 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 311 ms / 2,000 ms |
コード長 | 1,712 bytes |
コンパイル時間 | 2,343 ms |
コンパイル使用メモリ | 77,764 KB |
実行使用メモリ | 109,240 KB |
最終ジャッジ日時 | 2023-10-17 17:38:01 |
合計ジャッジ時間 | 10,925 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 271 ms
104,752 KB |
testcase_01 | AC | 278 ms
104,716 KB |
testcase_02 | AC | 286 ms
104,720 KB |
testcase_03 | AC | 280 ms
104,708 KB |
testcase_04 | AC | 281 ms
104,720 KB |
testcase_05 | AC | 276 ms
104,756 KB |
testcase_06 | AC | 279 ms
104,736 KB |
testcase_07 | AC | 282 ms
104,720 KB |
testcase_08 | AC | 267 ms
104,728 KB |
testcase_09 | AC | 288 ms
104,708 KB |
testcase_10 | AC | 274 ms
104,728 KB |
testcase_11 | AC | 269 ms
104,716 KB |
testcase_12 | AC | 268 ms
104,756 KB |
testcase_13 | AC | 287 ms
104,732 KB |
testcase_14 | AC | 285 ms
104,748 KB |
testcase_15 | AC | 278 ms
104,760 KB |
testcase_16 | AC | 277 ms
102,800 KB |
testcase_17 | AC | 291 ms
105,048 KB |
testcase_18 | AC | 302 ms
105,100 KB |
testcase_19 | AC | 305 ms
109,240 KB |
testcase_20 | AC | 302 ms
105,132 KB |
testcase_21 | AC | 311 ms
109,240 KB |
testcase_22 | AC | 275 ms
104,736 KB |
testcase_23 | AC | 293 ms
107,168 KB |
testcase_24 | AC | 293 ms
105,052 KB |
testcase_25 | AC | 299 ms
109,216 KB |
ソースコード
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { new Main().run(); } final long MOD = (long) 1e9 + 7; long[] fac = new long[2000000]; long[] ifac = new long[2000000]; long[] inv = new long[2000000]; { fac[0] = ifac[0] = inv[0] = fac[1] = ifac[1] = inv[1] = 1; for (int i = 2; i < fac.length; ++i) { fac[i] = fac[i - 1] * i % MOD; } // 0 = p/i*i + (p%i) for (int i = 2; i < inv.length; ++i) { inv[i] = MOD - inv[(int) (MOD % i)] * (MOD / i) % MOD; } for (int i = 2; i < ifac.length; ++i) { ifac[i] = inv[i] * ifac[i - 1] % MOD; } } long comb(int n, int k) { return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; } void run() throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); if (N == 1) { System.out.println(1); return; } long ans = 0; int[] a = new int[M + 2]; a[0] = 1; for (int i = 1; i <= N; ++i) { for (int j = 0; i + j < a.length; j += 2 * N) { a[i + j] = i; if (i + j + N < a.length) a[i + j + N] = N + 1 - i; } } for (int i = 1; i < a.length; ++i) { if (a[i] != 1) continue; int r = i - 1; if (r % 2 != M % 2) continue; if (M - r < 0) continue; int l = (M - r) / 2; r += l; ans = (ans + comb(l + r, l)) % MOD; } for (int i = 1; i < a.length; ++i) { if (a[i] != 1) continue; int r = i; if (r % 2 != M % 2) continue; if (M - r < 0) continue; int l = (M - r) / 2; r += l; ans = (ans + comb(l + r, l)) % MOD; } System.out.println(ans); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }