結果
問題 | No.1685 One by One |
ユーザー | 👑 hitonanode |
提出日時 | 2021-08-14 02:36:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,410 ms / 3,000 ms |
コード長 | 1,867 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 86,956 KB |
実行使用メモリ | 454,272 KB |
最終ジャッジ日時 | 2023-09-12 06:24:12 |
合計ジャッジ時間 | 47,098 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,388 KB |
testcase_01 | AC | 76 ms
71,456 KB |
testcase_02 | AC | 106 ms
77,096 KB |
testcase_03 | AC | 465 ms
156,504 KB |
testcase_04 | AC | 287 ms
128,756 KB |
testcase_05 | AC | 1,161 ms
277,380 KB |
testcase_06 | AC | 954 ms
267,696 KB |
testcase_07 | AC | 771 ms
211,084 KB |
testcase_08 | AC | 358 ms
160,488 KB |
testcase_09 | AC | 160 ms
88,764 KB |
testcase_10 | AC | 1,849 ms
405,560 KB |
testcase_11 | AC | 232 ms
85,876 KB |
testcase_12 | AC | 220 ms
112,608 KB |
testcase_13 | AC | 1,029 ms
270,336 KB |
testcase_14 | AC | 275 ms
111,088 KB |
testcase_15 | AC | 1,632 ms
350,864 KB |
testcase_16 | AC | 512 ms
202,824 KB |
testcase_17 | AC | 461 ms
183,744 KB |
testcase_18 | AC | 459 ms
183,472 KB |
testcase_19 | AC | 430 ms
183,096 KB |
testcase_20 | AC | 513 ms
182,076 KB |
testcase_21 | AC | 563 ms
183,796 KB |
testcase_22 | AC | 587 ms
200,204 KB |
testcase_23 | AC | 655 ms
202,636 KB |
testcase_24 | AC | 1,815 ms
399,336 KB |
testcase_25 | AC | 2,192 ms
431,660 KB |
testcase_26 | AC | 2,116 ms
421,324 KB |
testcase_27 | AC | 1,990 ms
406,380 KB |
testcase_28 | AC | 2,240 ms
454,272 KB |
testcase_29 | AC | 2,410 ms
453,936 KB |
testcase_30 | AC | 2,202 ms
453,504 KB |
testcase_31 | AC | 2,358 ms
454,024 KB |
testcase_32 | AC | 2,335 ms
453,756 KB |
testcase_33 | AC | 2,327 ms
454,048 KB |
testcase_34 | AC | 465 ms
203,156 KB |
testcase_35 | AC | 471 ms
203,032 KB |
testcase_36 | AC | 464 ms
203,020 KB |
testcase_37 | AC | 463 ms
202,028 KB |
testcase_38 | AC | 582 ms
202,996 KB |
testcase_39 | AC | 587 ms
202,992 KB |
testcase_40 | AC | 632 ms
202,316 KB |
testcase_41 | AC | 635 ms
203,220 KB |
testcase_42 | AC | 75 ms
71,040 KB |
testcase_43 | AC | 75 ms
71,288 KB |
testcase_44 | AC | 74 ms
71,256 KB |
testcase_45 | AC | 75 ms
71,372 KB |
testcase_46 | AC | 1,033 ms
284,272 KB |
testcase_47 | AC | 1,015 ms
284,292 KB |
testcase_48 | AC | 1,021 ms
283,908 KB |
testcase_49 | AC | 1,013 ms
284,040 KB |
ソースコード
N, M = map(int, input().split()) md = 1000000007 ncrs = [[0] * (max(N, M) + 10) for _ in range(N + M + 1)] ncrs[0][0] = 1 for i in range(1, len(ncrs)): ncrs[i][0] = 1 for j in range(1, len(ncrs[i])): ncrs[i][j] = ncrs[i - 1][j - 1] + ncrs[i - 1][j] if ncrs[i][j] >= md: ncrs[i][j] -= md precalc = [[0] * (M + 1) for _ in range(N + 1)] precalc[0][0] = 1 for n in range(N + 1): for m in range(M + 1): if n + m - 1 >= 0: precalc[n][m] = ncrs[n + m - 1][n - 1] if m >= 2: precalc[n][m] += precalc[n][m - 2] if precalc[n][m] >= md: precalc[n][m] -= md ret = 0 if N % 2 == 0: half = (N - 1) // 2 for nnonzero in range(half * 2 + 1): coeff = 0 for npos in range(half + 1): if nnonzero - npos < 0 or nnonzero - npos > half: continue coeff += ncrs[N - 1][npos] * ncrs[N - 1 - npos][nnonzero - npos] coeff %= md tmp = 0 for b0 in range(M + 1): if M - nnonzero - b0 < 0: break tmp += precalc[nnonzero][M - nnonzero - b0] * (2 - (b0 == 0)) ret += tmp % md * coeff ret %= md else: for npos in range(N // 2 + 1): for nneg in range(N // 2 + 1): nnonzero = npos + nneg coeff = 0 if M - (npos + nneg) >= 0: coeff += precalc[nnonzero][M - nnonzero] m = M - npos - (N - nneg) if m >= 0: coeff += precalc[nnonzero][m] * 2 m = M - (N - nnonzero) - (npos if npos > nneg else nneg) * 2 if m >= 0: coeff += md - precalc[nnonzero][m] ret += ncrs[N][nnonzero] * ncrs[nnonzero][npos] % md * coeff % md print(ret % md)