結果
問題 | No.834 Random Walk Trip |
ユーザー | 37zigen |
提出日時 | 2019-05-25 01:07:02 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 1,527 bytes |
コンパイル時間 | 4,179 ms |
コンパイル使用メモリ | 77,664 KB |
実行使用メモリ | 109,320 KB |
最終ジャッジ日時 | 2023-10-17 17:38:33 |
合計ジャッジ時間 | 11,145 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 268 ms
104,664 KB |
testcase_01 | AC | 274 ms
104,672 KB |
testcase_02 | AC | 287 ms
104,640 KB |
testcase_03 | AC | 285 ms
104,668 KB |
testcase_04 | AC | 286 ms
104,668 KB |
testcase_05 | AC | 292 ms
104,676 KB |
testcase_06 | AC | 289 ms
104,656 KB |
testcase_07 | AC | 298 ms
104,668 KB |
testcase_08 | AC | 298 ms
104,672 KB |
testcase_09 | AC | 291 ms
104,660 KB |
testcase_10 | AC | 290 ms
104,656 KB |
testcase_11 | AC | 296 ms
102,800 KB |
testcase_12 | AC | 306 ms
104,660 KB |
testcase_13 | AC | 295 ms
104,644 KB |
testcase_14 | AC | 293 ms
104,672 KB |
testcase_15 | AC | 282 ms
104,668 KB |
testcase_16 | AC | 290 ms
104,656 KB |
testcase_17 | AC | 314 ms
105,164 KB |
testcase_18 | AC | 319 ms
105,204 KB |
testcase_19 | AC | 309 ms
109,320 KB |
testcase_20 | AC | 302 ms
105,232 KB |
testcase_21 | AC | 317 ms
109,316 KB |
testcase_22 | AC | 298 ms
104,692 KB |
testcase_23 | AC | 314 ms
106,724 KB |
testcase_24 | AC | 302 ms
105,164 KB |
testcase_25 | AC | 321 ms
108,772 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; for (int d = 0; d <= 1; ++d) { int r = i - d; 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)); } }