Submission #65693279

---

Source Code Expand

# 高速なの　O(N)
from itertools import permutations


class Binominal:
    def __init__(self, N, mod) -> None:
        fact = [1, 1]
        factinv = [1, 1]
        inv = [0, 1]

        for i in range(2, N + 1):
            fact.append((fact[-1] * i) % mod)
            inv.append((-inv[mod % i] * (mod // i)) % mod)
            factinv.append((factinv[-1] * inv[-1]) % mod)

        self.fact = fact
        self.factinv = factinv
        self.inv = inv
        self.mod = mod
        self.N = N

    def nPr(self, n, r):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod

    def nCr(self, n, r):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return (
            self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
        )


MOD = 998244353


def main():
    A, B, C, D = map(int, input().split())

    ans = solve(A, B, C, D)
    print(ans)


def solve(A, B, C, D):
    bn = Binominal(A + B + C + D, MOD)
    ans = 0
    for b in range(B + 1):
        ans += bn.nCr(A + b - 1, b) * bn.nCr(B - b + C + D, C) % MOD
        ans %= MOD
    return ans


def naive(A, B, C, D):
    ans = 0
    cand = list("a" * A) + list("b" * B) + list("c" * C) + list("d" * D)
    seen = set()
    for pat in permutations(cand):
        s = "".join(pat)
        if s.rindex("a") > s.index("d"):
            continue
        if s.rindex("a") > s.index("c"):
            continue
        if s.rindex("b") > s.index("d"):
            continue
        seen.add(s)
    print(*seen, sep="\n")
    return len(seen)


def test():

    print(solve(2, 1, 1, 1), naive(2, 1, 1, 1))
    print(solve(1, 1, 1, 2), naive(1, 1, 1, 2))
    print(naive(1, 1, 1, 1))


# test()
main()


"""
補集合を考えた方が楽そう？

制約がないパターン数
(ABCD)C(A) (BCD)C(B) (CD)C(C)

"""

Submission Info

Judge Result