問題
$N$ 個のボールから $K$ 個を選ぶ組み合わせの数を $10^9 + 7$ で割った余りを求めてください。
入力形式
N K制約
$0 \le K \le N \le 10^6$
入出力例
入力例 1
5 2出力例 1
10入力例 2
1000000 500000出力例 2
149033233ヒント (段階的開示)
ヒント1: 方向性
$C(N, K) = N! / (K! \times (N-K)!)$ ですが、大きな数の除算は mod では直接できません。
ヒント2: アプローチ
mod $p$ での除算は「逆元」を使います。フェルマーの小定理より、$p$ が素数のとき $a^{p-2} \equiv a^{-1} \pmod{p}$ が成り立ちます。
ヒント3: 誘導
MOD = 10**9 + 7
# 前計算: 階乗と逆元の階乗テーブル
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD) # フェルマーの小定理
for i in range(N - 1, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
def comb(n, k):
if k < 0 or k > n: return 0
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N, K = map(int, input().split())
MOD = 10**9 + 7
# 前計算: 0〜N の階乗テーブル
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i-1] * i % MOD
# 逆元の階乗テーブル（フェルマーの小定理で計算）
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
def comb(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD
print(comb(N, K))
main()Step-by-Step 解説
1mod での除算の問題
$10^9$ 規模の $N$ では $N!$ が巨大になり、直接除算すると mod 演算を壊します。逆元を使って「除算」を「乗算」に変換します。
$10^9$ 規模の $N$ では $N!$ が巨大になり、直接除算すると mod 演算を壊します。逆元を使って「除算」を「乗算」に変換します。
2フェルマーの小定理
素数 $p$ に対して $a^{p-1} \equiv 1 \pmod{p}$ が成り立つため、$a \times a^{p-2} \equiv 1 \pmod{p}$ → $a^{-1} \equiv a^{p-2} \pmod{p}$。
素数 $p$ に対して $a^{p-1} \equiv 1 \pmod{p}$ が成り立つため、$a \times a^{p-2} \equiv 1 \pmod{p}$ → $a^{-1} \equiv a^{p-2} \pmod{p}$。
3逆元テーブルを O(N) で構築
個別に
個別に
pow(fact[i], MOD-2, MOD) を呼ぶと $O(N \log p)$ になる。代わりに後ろから inv_fact[i] = inv_fact[i+1] * (i+1) % MOD で $O(N)$ に短縮。
4組み合わせの計算
$C(n, k) = n! \times (k!)^{-1} \times ((n-k)!)^{-1} \bmod p$
$C(n, k) = n! \times (k!)^{-1} \times ((n-k)!)^{-1} \bmod p$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
N! % MOD を先に計算してから除算 | mod後は整数除算不可 | 逆元を使う |
pow(a, MOD-2, MOD) でなく普通のべき乗 | Python組み込みの pow(a, b, m) が高速 | pow(a, MOD-2, MOD) |
k > n のケースを考慮しない | C(n, k) = 0 になる | if k < 0 or k > n: return 0 |
次のステップ
- 発展問題: パスカルの三角形で $C(N, K)$ を $O(N^2)$ DP で求める（$N$ が小さい場合）