任意 mod の二項係数
$m = p_1^{e_1} p_2^{e_2} \cdots$ と素因数分解し、 $q = p^e$ ごとに $\binom{n}{k} \bmod q$ を求めてから中国剰余定理でまとめます。 $\binom{n}{k}$ を割り切る $p$ の指数 $v$ は、 $k$ と $n - k$ を $p$ 進数で足したときの繰り上がりの回数です(Kummer の定理)。 $v \ge e$ なら $\binom{n}{k} \equiv 0 \pmod{q}$ です。
$n!$ を $p$ で割れるだけ割ったものを $F(n)$、 $1$ 以上 $i$ 以下で $p$ の倍数でない整数の積を $q$ で割った余りを $T(i)$ とすると、 $F(n) \equiv T(q - 1)^{\lfloor n / q \rfloor} T(n \bmod q) F(\lfloor n / p \rfloor) \pmod{q}$ が成り立ちます。 $T(q - 1)$ は $p = 2$, $e \ge 3$ のときだけ $1$ で、それ以外は $-1$ です。 $q$ 未満の $T$ の表を前計算しておけば、 $\binom{n}{k} \equiv p^v F(n) / (F(k) F(n - k)) \pmod{q}$ を、 $n$ を $p$ で割っていきながら求められます(Granville による Lucas の定理の拡張)。
BinomialAnyMod(m): $m \ge 1$ を法として前計算する。 $m$ を割り切る素数べき $q$ ごとに長さ $q$ の表を作る。 $O(m)$C(n, k): $\binom{n}{k} \bmod m$( $k < 0$ や $k > n$ のときは $0$)。 $0 \le n \le 10^{18}$ でよい。 $O(\omega(m) \log n)$( $\omega(m)$ は $m$ の素因数の種類数)
表の大きさの合計は $m$ 以下なので、 $m$ は $10^7$ 程度までが目安です。 $m$ が $998244353$ のような大きい素数で $n$ が小さいときは 二項係数 (nCr) を、 $m$ が小さい素数なら Lucas の定理 を使っても求められます。
例:
B = BinomialAnyMod(pow(10, 6))
print(B.C(100, 50)) # 497256
print(B.C(pow(10, 18) - 1, 12345)) # 499999
コード
class BinomialAnyMod:
# 任意の m (>= 1) を法とする二項係数。m を割り切る素数べき p^e ごとに求めて、中国剰余定理でまとめる
def __init__(self, m):
self.m = m
self.ps = [] # (p, e, q = p^e, 中国剰余定理の係数, 表)
x = m
p = 2
while x > 1:
if p * p > x:
p = x # 残りは素数
if x % p == 0:
e = 0
q = 1
while x % p == 0:
x //= p
e += 1
q *= p
# fact[i] = (1 以上 i 以下で p の倍数でない整数の積) mod q
fact = [1] * q
for i in range(1, q):
fact[i] = fact[i - 1] if i % p == 0 else fact[i - 1] * i % q
r = m // q
coef = r * pow(r, -1, q) % m # mod q で 1、mod m / q で 0
self.ps.append((p, e, q, coef, fact))
p += 1
def C(self, n, k):
# nCk mod m
if k < 0 or k > n:
return 0
res = 0
for p, e, q, coef, fact in self.ps:
a, b, c = n, k, n - k
num = den = 1
v = 0 # nCk を割り切る p の指数(k と n - k を p 進数で足したときの繰り上がりの回数)
s = 0 # e 桁目より上への繰り上がりの回数の偶奇(符号を決める)
j = 0
# n! から p を除いた部分 = (1 以上 q 以下で p の倍数でない整数の積)^(n // q) * fact[n % q] * (n // p)! から p を除いた部分
# b か c が 0 で、下の桁からの繰り上がりもなければ、残りの桁は 1 を掛けるだけ
while (b and c) or a > b + c:
num = num * fact[a % q] % q
den = den * fact[b % q] % q * fact[c % q] % q
a //= p
b //= p
c //= p
j += 1
if a - b - c:
v += 1
if v == e:
break
if j >= e:
s ^= 1
if v == e:
continue # mod q で 0
x = num * pow(den, -1, q) % q * pow(p, v) % q
if s:
x = x * fact[q - 1] % q # fact[q - 1] は ±1(p = 2, e >= 3 のときだけ 1)
res += x * coef
return res % self.m