問題
素数 $p$（$10^9 \le p \le 2 \times 10^9$）と整数 $N, K$ が与えられる（$N < p$）。二項係数 $C(N, K) \bmod p$ を求めよ。$p$ は固定の素数ではないことに注意。
制約
$0 \le K \le N \le 10^{18}$
$10^9 \le p \le 2 \times 10^9$（素数）
$N < p$ 保証
入出力例
入力例 1
10 3 1000000007出力例 1
120ヒント (段階的開示)
ヒント1: 方向性
$N < p$ なら Lucas 不要。フェルマー小定理で逆元を作り、$C(N,K) = N!/(K!(N-K)!)$ を計算。$N$ が $10^{18}$ なので $N!$ は不可能。
ヒント2: アプローチ
$C(N,K) = N(N-1)\cdots(N-K+1)/K!$。対称性 $C(N,K)=C(N,N-K)$ で $\min(K, N-K)$ 個の積に。
ヒント3: 誘導
def modinv(a, p):
return pow(a, p - 2, p)
def comb_mod(n, k, p):
if k > n - k: k = n - k
num = 1
for i in range(k):
num = num * ((n - i) % p) % p
den = 1
for i in range(1, k + 1):
den = den * i % p
return num * modinv(den, p) % p模範解答 (Python)
import sys
input = sys.stdin.readline
def modinv(a, p):
return pow(a, p - 2, p)
def comb_mod(n, k, p):
if k < 0 or k > n:
return 0
if k > n - k:
k = n - k
num = 1
for i in range(k):
num = num * ((n - i) % p) % p
den = 1
for i in range(1, k + 1):
den = den * (i % p) % p
return num * modinv(den, p) % p
line = input().split()
N, K, p = int(line[0]), int(line[1]), int(line[2])
print(comb_mod(N, K, p))Step-by-Step 解説
1二項係数の変形
$C(N,K) = N(N-1)\cdots(N-K+1)/K!$（分子は K 個の積）。
$C(N,K) = N(N-1)\cdots(N-K+1)/K!$（分子は K 個の積）。
2対称性
$C(N,K)=C(N,N-K)$。$K > N/2$ なら置換して分子の積を減らす。
$C(N,K)=C(N,N-K)$。$K > N/2$ なら置換して分子の積を減らす。
3モジュラ逆元
$K!^{-1} \equiv (K!)^{p-2} \pmod{p}$（フェルマー小定理、$N < p$ から $K! \not\equiv 0$）。
$K!^{-1} \equiv (K!)^{p-2} \pmod{p}$（フェルマー小定理、$N < p$ から $K! \not\equiv 0$）。
4計算量
$O(\min(K, N-K))$。
$O(\min(K, N-K))$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
(n-i) % p 忘れ | 中間値が p より大きい | num * ((n - i) % p) % p |
| K ≥ p で K! ≡ 0 | 逆元なし | N < p の制約を確認 |
| 対称性を使わない | K が大きいまま loop | if k > n-k: k = n-k |
次のステップ
- Lucas の定理（N ≥ p の場合）
- Andrew Granville の方法（p が素数でない場合）