二項係数 (nCr)

$0!$ から $N!$ までの階乗とその逆元を前計算します。 mod は $N$ より大きい素数である必要があります。

• Combination(N, mod): 前計算。 mod の既定値は $998244353$。 $O(N)$
• C(n, r): $\binom{n}{r}$。 $r < 0$ や $r > n$ のときは $0$
• P(n, r): $\frac{n!}{(n-r)!}$
• H(n, r): 重複組合せ $\binom{n+r-1}{r}$（ $n + r - 1 \le N$ の範囲で使う）
• inv(n): $n^{-1}$（ $1 \le n \le N$）
• 計算量: 各クエリ $O(1)$

コード

class Combination:
    def __init__(self, n, mod=998244353):
        self.mod = mod
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.inv_fact = [1] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in range(n, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % mod

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

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

    def H(self, n, r):
        if n == 0 and r == 0:
            return 1
        return self.C(n + r - 1, r)

    def inv(self, n):
        return self.inv_fact[n] * self.fact[n - 1] % self.mod