結果

問題 No.1685 One by One
ユーザー hitonanodehitonanode
提出日時 2021-08-14 02:30:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 939 ms / 3,000 ms
コード長 2,282 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 202,820 KB
最終ジャッジ日時 2024-06-29 19:26:53
合計ジャッジ時間 17,214 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,224 KB
testcase_01 AC 40 ms
52,480 KB
testcase_02 AC 65 ms
69,632 KB
testcase_03 AC 183 ms
91,968 KB
testcase_04 AC 104 ms
82,048 KB
testcase_05 AC 519 ms
137,856 KB
testcase_06 AC 291 ms
113,152 KB
testcase_07 AC 368 ms
114,304 KB
testcase_08 AC 69 ms
68,224 KB
testcase_09 AC 99 ms
80,640 KB
testcase_10 AC 703 ms
179,328 KB
testcase_11 AC 106 ms
78,848 KB
testcase_12 AC 74 ms
71,936 KB
testcase_13 AC 427 ms
119,716 KB
testcase_14 AC 134 ms
85,376 KB
testcase_15 AC 691 ms
162,576 KB
testcase_16 AC 88 ms
74,624 KB
testcase_17 AC 81 ms
74,812 KB
testcase_18 AC 88 ms
74,664 KB
testcase_19 AC 56 ms
64,896 KB
testcase_20 AC 158 ms
72,192 KB
testcase_21 AC 174 ms
77,312 KB
testcase_22 AC 200 ms
82,944 KB
testcase_23 AC 220 ms
83,180 KB
testcase_24 AC 712 ms
182,548 KB
testcase_25 AC 892 ms
192,476 KB
testcase_26 AC 753 ms
183,680 KB
testcase_27 AC 831 ms
185,152 KB
testcase_28 AC 827 ms
201,972 KB
testcase_29 AC 935 ms
202,820 KB
testcase_30 AC 825 ms
201,948 KB
testcase_31 AC 932 ms
202,652 KB
testcase_32 AC 937 ms
202,496 KB
testcase_33 AC 939 ms
202,368 KB
testcase_34 AC 54 ms
63,744 KB
testcase_35 AC 52 ms
63,488 KB
testcase_36 AC 51 ms
62,848 KB
testcase_37 AC 51 ms
63,104 KB
testcase_38 AC 164 ms
67,840 KB
testcase_39 AC 158 ms
68,608 KB
testcase_40 AC 177 ms
73,856 KB
testcase_41 AC 178 ms
74,240 KB
testcase_42 AC 39 ms
52,352 KB
testcase_43 AC 38 ms
52,352 KB
testcase_44 AC 37 ms
52,736 KB
testcase_45 AC 38 ms
52,736 KB
testcase_46 AC 306 ms
114,688 KB
testcase_47 AC 305 ms
114,620 KB
testcase_48 AC 306 ms
114,432 KB
testcase_49 AC 302 ms
114,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools
N, M = map(int, input().split())

class facmod:
    def __init__(self, N: int, md: int) -> None:
        assert N < md
        self.md = md
        self.facs = [1] * (N + 1)
        self.facinvs = [1] * (N + 1)
        for i in range(1, N + 1):
            self.facs[i] = self.facs[i - 1] * i % md
        self.facinvs[N] = pow(self.facs[i], md - 2, md)
        for i in range(N - 1, 0, -1):
            self.facinvs[i] = self.facinvs[i + 1] * (i + 1) % md

    def nCr(self, n: int, r: int) -> int:
        if n < 0 or r < 0 or n < r:
            return 0
        return (self.facs[n] * self.facinvs[r]) % md * self.facinvs[n - r] % md

md = 1000000007
fac = facmod(N + M, 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] = fac.nCr(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 += fac.nCr(N - 1, npos) * fac.nCr(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 += fac.nCr(N, nnonzero) * fac.nCr(nnonzero, npos) % md * (coeff % md)
            ret %= md

print(ret)
0