結果

問題 No.1685 One by One
ユーザー hitonanodehitonanode
提出日時 2021-08-14 02:36:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,277 ms / 3,000 ms
コード長 1,867 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 81,840 KB
実行使用メモリ 452,984 KB
最終ジャッジ日時 2024-06-29 19:28:35
合計ジャッジ時間 42,818 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,696 KB
testcase_01 AC 40 ms
52,508 KB
testcase_02 AC 71 ms
70,632 KB
testcase_03 AC 424 ms
157,188 KB
testcase_04 AC 248 ms
127,304 KB
testcase_05 AC 1,085 ms
276,164 KB
testcase_06 AC 864 ms
266,044 KB
testcase_07 AC 706 ms
203,460 KB
testcase_08 AC 310 ms
159,948 KB
testcase_09 AC 124 ms
89,072 KB
testcase_10 AC 1,708 ms
404,340 KB
testcase_11 AC 113 ms
84,752 KB
testcase_12 AC 188 ms
111,436 KB
testcase_13 AC 972 ms
268,460 KB
testcase_14 AC 237 ms
111,440 KB
testcase_15 AC 1,552 ms
350,044 KB
testcase_16 AC 470 ms
203,256 KB
testcase_17 AC 421 ms
183,828 KB
testcase_18 AC 427 ms
183,312 KB
testcase_19 AC 395 ms
183,768 KB
testcase_20 AC 480 ms
180,892 KB
testcase_21 AC 526 ms
184,232 KB
testcase_22 AC 547 ms
198,928 KB
testcase_23 AC 620 ms
203,196 KB
testcase_24 AC 1,764 ms
398,060 KB
testcase_25 AC 2,072 ms
430,732 KB
testcase_26 AC 1,872 ms
420,248 KB
testcase_27 AC 1,918 ms
404,864 KB
testcase_28 AC 2,130 ms
452,416 KB
testcase_29 AC 2,248 ms
452,984 KB
testcase_30 AC 2,078 ms
452,108 KB
testcase_31 AC 2,271 ms
452,780 KB
testcase_32 AC 2,242 ms
452,340 KB
testcase_33 AC 2,277 ms
452,632 KB
testcase_34 AC 424 ms
202,136 KB
testcase_35 AC 426 ms
201,400 KB
testcase_36 AC 423 ms
201,796 KB
testcase_37 AC 398 ms
183,640 KB
testcase_38 AC 536 ms
202,528 KB
testcase_39 AC 546 ms
202,064 KB
testcase_40 AC 583 ms
201,340 KB
testcase_41 AC 601 ms
202,208 KB
testcase_42 AC 37 ms
52,668 KB
testcase_43 AC 38 ms
52,556 KB
testcase_44 AC 36 ms
53,312 KB
testcase_45 AC 37 ms
53,256 KB
testcase_46 AC 962 ms
283,072 KB
testcase_47 AC 966 ms
283,308 KB
testcase_48 AC 976 ms
282,620 KB
testcase_49 AC 966 ms
282,980 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0