combination, 逆元の計算

combination, 逆元

階乗、逆元を事前に計算しておくことで$_{n}C_k$を$O(1)$で計算できる。

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

AtCoder Regular Contest 077 D 11
https://arc077.contest.atcoder.jp/tasks/arc077_b