< AP25さんのAI生成コード置き場

二項係数計算

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

mod = 998244353   
nmax = 2 * 10 ** 5

fact = [1] * (nmax + 1)
invfact = [1] * (nmax + 1)

# 1. 階乗を計算
for i in range(1, nmax + 1):
    fact[i] = (fact[i - 1] * i) % mod

# 2. 最大の階乗 n! の逆元をフェルマーの小定理で求める
# pow(a, b, m) は (a^b) % m
invfact[nmax] = pow(fact[nmax], mod - 2, mod)

# 3. 逆順に計算して全ての階乗の逆元を求める
# (n-1)!^-1 = n!^-1 * n
for i in range(nmax - 1, -1, -1):
    invfact[i] = (invfact[i + 1] * (i + 1)) % mod

# r < 0 or r > n で 0を返すことに注意
def nCr(n,r):
    if r < 0 or r > n:
        return 0
    ret = fact[n] * invfact[r] * invfact[n-r] % mod
    return ret