Problem link ও উৎস
- **Original source:** CP-Algorithms — Binomial Coefficients
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Hard
- **Pattern:** factorial + inverse (nCr mod p pipeline)
- **Basic idea inherited from:** 032 — Modular Inverse Basic; সঙ্গে 039 — Factorial (Level 3)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো সংখ্যা `n` আর `r` (`0 ≤ r ≤ n`) আর একটা **prime** `p` দেওয়া। বের করতে হবে **nCr (binomial coefficient) mod p** — মানে:
`C(n, r) = n! / (r! × (n−r)!)`, উত্তরটা `% p`
সমস্যা: `n` বড় হলে (যেমন 10⁶) `n!` প্রকাণ্ড, আর mod-জগতে সরাসরি **ভাগ নেই**। তাই ভাগের জায়গায় inverse দিয়ে গুণ করতে হবে। আর অনেক query (n, r জোড়া) এলে প্রতিবার নতুন করে হিসাব না করে precompute চাই।
### Input ও output {#6-example-input-and-output}
```text
n r p (prime) -> C(n,r) % p check
---------------------------------------------------------
5 2 7 -> 3 C(5,2)=10, 10%7=3
10 3 1000000007 -> 120 C(10,3)=120
6 0 7 -> 1 C(n,0)=1 সবসময়
6 6 7 -> 1 C(n,n)=1
5 7 7 -> 0 r > n -> 0
100 50 1000000007 -> বিশাল mod (math.comb দিয়ে মিলাও)
```
edge case: `r > n` বা `r < 0` হলে `C = 0`। আর `C(n, 0) = C(n, n) = 1` সবসময়। বড় `n`-এও pipeline মুহূর্তে দেয় কারণ precompute হয়ে আছে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা **রান্নাঘর আগে থেকে গুছিয়ে রাখছ** যাতে যেকোনো অর্ডার চটজলদি দিতে পারো। আগে থেকে কেটে রাখা সবজি (`fact[]`) আর আগে থেকে বানানো sauce (`inv_fact[]`) — দুটো prep একবার করো (O(N))।
তারপর যত অর্ডারই আসুক (`C(n, r)` query), প্রতিটা শুধু তিনটে জিনিস তুলে গুণে দিলেই হলো — `fact[n] × inv_fact[r] × inv_fact[n−r]` — কয়েক সেকেন্ডে (O(1))। prep ছাড়া প্রতি অর্ডারে নতুন করে সব কাটাকুটি (factorial + inverse) করলে রেস্তোরাঁ ডুবে যেত। precompute-এর পুরো দর্শন এটাই: একবার খাটো, বারবার সুফল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো শিকড়:
- **032 — Modular Inverse Basic:** ভাগের বদলে inverse দিয়ে গুণ — এই note-এর হৃদয়। inv_fact বের করা সরাসরি Fermat inverse।
- **039 — Factorial (Level 3):** nCr-এর সংজ্ঞাই factorial দিয়ে; এখানে সেই factorial-কে mod-এ precompute করছি (028-এর factorial_mod-এর array রূপ)।
আর পেছনে 028 (প্রতি গুণে mod) আর 029 (fast power, কারণ Fermat inverse তার উপর দাঁড়ায়)। মানে এই Hard problem আসলে আগের ৬-৭টা note-এর জোট — তাই আলাদা করে কঠিন কিছু নয়, শুধু একসাথে সাজানো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **factorial precompute + modular inverse**। mod-এ ভাগ নেই, তাই:
`C(n, r) mod p = fact[n] × inv_fact[r] × inv_fact[n−r] (সব mod p)`
যেখানে `fact[i] = i! mod p` আর `inv_fact[i] = (i!)⁻¹ mod p` (inverse factorial)।
দুটো চাবি:
1. **factorial-mod** (028): `fact[i] = fact[i−1] × i % p` — O(N)-তে সব factorial।
2. **Fermat inverse** (032): `inv_fact[N] = pow(fact[N], p−2, p)`, তারপর পেছন থেকে `inv_fact[i−1] = inv_fact[i] × i % p` — মাত্র **একটা** Fermat call দিয়ে সব inverse factorial।
ভাগ → inverse দিয়ে গুণ; এটাই পুরো গল্প।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল (Python-এই): সরাসরি সংজ্ঞা — factorial বানিয়ে integer ভাগ, তারপর mod। অথবা mod-জগতে প্রতি query-তে নতুন করে factorial + Fermat inverse।
```python
def ncr_brute(n, r, p):
if r < 0 or r > n:
return 0
# পুরো factorial integer-এ, তারপর সাধারণ ভাগ, শেষে mod
num = den = 1
for i in range(1, n + 1):
num *= i
for i in range(1, r + 1):
den *= i
for i in range(1, n - r + 1):
den *= i
return (num // den) % p
```
Python-এ ঠিক উত্তর দেয় (big int + integer division)। কিন্তু প্রতি query-তে পুরো `n!` বানায় — বিশাল।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো সমস্যা:
1. **বিশাল factorial:** `n = 10⁶` হলে `n!` প্রায় 5.5 মিলিয়ন digit — প্রতিটা গুণ ভয়াবহ ধীর, একটা query-তেই সেকেন্ড। C++/Java-তে integer division-এর আগে overflow।
2. **প্রতি query-তে পুনরাবৃত্তি:** q টা query থাকলে প্রতিবার আবার পুরো factorial — মোট O(q × n) বা তারও বেশি। CP-তে q, n দুটোই 10⁵-10⁶ হলে অসম্ভব।
```text
q = 10^5 query, n পর্যন্ত 10^6:
brute: প্রতি query-তে পুরো n! -> O(q × n) বিশাল-সংখ্যা গুণ, অচল
precompute: একবার O(N) prep, তারপর প্রতি query O(1) -> মোট O(N + q)
```
মূল শিক্ষা: একই factorial বারবার না বানিয়ে একবার precompute করো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
pipeline তিন ধাপে — factorial precompute, inverse factorial (একটা Fermat call), তারপর প্রতি query O(1):
```python
MOD = 10**9 + 7
def build_factorials(N, p=MOD):
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % p # ধাপ 1: O(N)
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], p - 2, p) # ধাপ 2a: একটা Fermat
for i in range(N, 0, -1): # ধাপ 2b: পেছন থেকে
inv_fact[i - 1] = inv_fact[i] * i % p # 1/(i-1)! = (1/i!) × i
return fact, inv_fact
def nCr(n, r, fact, inv_fact, p=MOD):
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p # ধাপ 3: O(1)
```
ধাপ 2-এর চালাকি: N টা আলাদা Fermat call (প্রতিটা O(log p))-এর বদলে **একটা** Fermat + N টা গুণ। `1/(i−1)! = (1/i!) × i` — কারণ `i! = (i−1)! × i`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
দুটো "আহা!":
1. **ভাগ → inverse দিয়ে গুণ।** mod-জগতে `n! / (r!(n−r)!)`-এর ভাগটা সরাসরি হয় না; প্রতিটা হরকে তার inverse দিয়ে বদলে গুণ করো। এটাই 032-এর সরাসরি প্রয়োগ।
2. **সব inverse factorial একটা Fermat-এই।** সবচেয়ে দামি tweak: শেষ inv_fact-টা Fermat-এ বের করে, পেছন থেকে হেঁটে বাকিগুলো শুধু একটা করে গুণে পাও (`inv_fact[i−1] = inv_fact[i] × i`)। N টা log-call থেকে 1 টা — contest-এ এটাই TLE আর AC-র তফাত।
### ছবিতে বোঝা {#5-visual-explanation}
`C(5, 2) mod 7` — সংজ্ঞা থেকে pipeline:
```text
C(5,2) = 5! / (2! × 3!) = 120 / (2 × 6) = 120 / 12 = 10
mod 7-এ: 10 % 7 = 3 (লক্ষ্য)
mod-এ ভাগ নেই, তাই:
C(5,2) mod 7 = fact[5] × inv_fact[2] × inv_fact[3] (mod 7)
```
precompute (mod 7):
```text
fact: [1, 1, 2, 6, 24%7=3, 120%7=1] -> fact[5]=1
inv_fact[5] = pow(fact[5], 5, 7) = pow(1,5,7) = 1
পেছন থেকে: inv_fact[4]=inv_fact[5]×5=5, inv_fact[3]=5×4=20%7=6,
inv_fact[2]=6×3=18%7=4, ...
C(5,2) = fact[5] × inv_fact[2] × inv_fact[3]
= 1 × 4 × 6 % 7 = 24 % 7 = 3 ✓ মিলল!
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`N = 5`, `p = 7`, লক্ষ্য `C(5, 2)`:
ধাপ 1 — factorial mod 7:
| i | fact[i-1] × i | % 7 |
| --- | --- | --- |
| 1 | 1 × 1 = 1 | 1 |
| 2 | 1 × 2 = 2 | 2 |
| 3 | 2 × 3 = 6 | 6 |
| 4 | 6 × 4 = 24 | 3 |
| 5 | 3 × 5 = 15 | 1 |
তাই `fact = [1, 1, 2, 6, 3, 1]`।
ধাপ 2 — inv_fact, `inv_fact[5] = pow(1, 5, 7) = 1`, পেছন থেকে:
| i | inv_fact[i] × i | % 7 → inv_fact[i-1] |
| --- | --- | --- |
| 5 | 1 × 5 = 5 | inv_fact[4] = 5 |
| 4 | 5 × 4 = 20 | inv_fact[3] = 6 |
| 3 | 6 × 3 = 18 | inv_fact[2] = 4 |
| 2 | 4 × 2 = 8 | inv_fact[1] = 1 |
| 1 | 1 × 1 = 1 | inv_fact[0] = 1 |
ধাপ 3 — query `C(5, 2)`:
```text
fact[5] × inv_fact[2] × inv_fact[3] % 7
= 1 × 4 × 6 % 7 = 24 % 7 = 3
```
উত্তর **3**। Check: C(5,2) = 10, `10 % 7 = 3` ✓। (যাচাই: inv_fact[2] = inverse(2!) = inverse(2) = 4, কারণ 2×4=8≡1 ✓; inv_fact[3] = inverse(6) = 6, কারণ 6×6=36≡1 ✓।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import math
MOD = 10**9 + 7
def build_factorials(N, p=MOD):
"""0..N পর্যন্ত fact ও inv_fact precompute — একটা মাত্র Fermat call।"""
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % p
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], p - 2, p) # Fermat inverse, একবার
for i in range(N, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % p # 1/(i-1)! = (1/i!) × i
return fact, inv_fact
def nCr(n, r, fact, inv_fact, p=MOD):
"""C(n, r) % p, precomputed table থেকে O(1)।"""
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p
# --- precompute একবার, তারপর অনেক query ---
N = 2000
fact, inv_fact = build_factorials(N, MOD)
# ছোট prime দিয়ে আলাদা যাচাই (dry run-এর সাথে মেলে):
# সাবধান: এই pipeline-এ N অবশ্যই p-এর ছোট হতে হবে, নাহলে fact[p] ≡ 0 হয়ে
# inverse ভেঙে পড়ে (Common mistakes দেখো)। p=7 হলে N সর্বোচ্চ 6।
f7, if7 = build_factorials(6, 7)
assert nCr(5, 2, f7, if7, 7) == 3 # C(5,2)=10 -> 10%7=3
assert nCr(6, 0, f7, if7, 7) == 1 # C(n,0)=1
assert nCr(6, 6, f7, if7, 7) == 1 # C(n,n)=1
assert nCr(5, 7, f7, if7, 7) == 0 # r > n -> 0
# inv_fact সত্যিই inverse কিনা: fact[i] × inv_fact[i] ≡ 1
for i in range(0, 7):
assert (f7[i] * if7[i]) % 7 == 1
# বড় prime-এ math.comb-এর সাথে মিলিয়ে দেখা — এটাই মূল যাচাই:
assert nCr(10, 3, fact, inv_fact, MOD) == math.comb(10, 3) % MOD
assert nCr(100, 50, fact, inv_fact, MOD) == math.comb(100, 50) % MOD
assert nCr(2000, 1000, fact, inv_fact, MOD) == math.comb(2000, 1000) % MOD
assert nCr(1500, 7, fact, inv_fact, MOD) == math.comb(1500, 7) % MOD
assert nCr(7, 10, fact, inv_fact, MOD) == 0 # r > n
print(nCr(5, 2, f7, if7, 7)) # 3
print(nCr(10, 3, fact, inv_fact, MOD)) # 120
print(nCr(100, 50, fact, inv_fact, MOD)) # বিশাল mod মান
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % p
```
ধাপ 1: `fact[i] = i! mod p`। আগেরটার সাথে `i` গুণ, প্রতি step-এ mod (028-এর factorial-mod-এর array রূপ)। `fact[0] = 1` (খালি গুণফল)।
```text
inv_fact[N] = pow(fact[N], p - 2, p)
for i in range(N, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % p
```
ধাপ 2: সবচেয়ে বড় inverse factorial-টা Fermat-এ (`fact[N]^(p−2)`)। তারপর পেছন থেকে — যেহেতু `i! = (i−1)! × i`, তাই `1/(i−1)! = (1/i!) × i`। মানে একটা Fermat + N গুণে সব inverse factorial।
```text
def nCr(n, r, fact, inv_fact, p=MOD):
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p
```
ধাপ 3: `r` সীমার বাইরে হলে 0। নাহলে `n! × (r!)⁻¹ × ((n−r)!)⁻¹` — ভাগের তিন অংশ inverse দিয়ে গুণ, প্রতি গুণে mod। এটাই O(1) query।
```text
for i in range(0, 11):
assert (f7[i] * if7[i]) % 7 == 1
...
assert nCr(...) == math.comb(...) % MOD
```
প্রথম loop নিশ্চিত করে `inv_fact` সত্যিই inverse (`fact × inv_fact ≡ 1`)। তারপর Python-এর সত্যিকার `math.comb`-এর সাথে বড় prime-এ মিলিয়ে দেখা — এটাই সবচেয়ে শক্ত যাচাই, mod-এর bug ধরার একমাত্র উপায়। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
120
... (একটা বিশাল mod মান)
সব test pass!
```
প্রথম লাইন `nCr(5, 2)` mod 7 → 3 (dry run-এর সাথে মেলে)। দ্বিতীয় `nCr(10, 3)` mod 10⁹+7 → 120 (C(10,3)=120, mod-এ অপরিবর্তিত যেহেতু ছোট)। তৃতীয় `nCr(100, 50)` → একটা বিশাল mod মান, কিন্তু O(1)-তে। আগের সব `assert` (`math.comb`-এর সাথে 2000-পর্যন্ত মিল সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
- **Precompute:** O(N) — factorial loop O(N), inverse factorial loop O(N), একটা Fermat O(log p)। মোট O(N + log p) ≈ O(N)।
- **প্রতি query:** O(1) — তিনটে array lookup আর দুটো গুণ।
- **মোট (q query):** O(N + q)। brute-এর O(q × n)-এর তুলনায় বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(N)** — `fact` আর `inv_fact` দুটো array, প্রতিটা N+1 দৈর্ঘ্য। এটাই precompute-এর দাম: সময় বাঁচাতে memory খরচ (classic time-space tradeoff)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **mod-এ সরাসরি ভাগ** — `fact[n] // (fact[r] * fact[n-r]) % p` ভুল; mod-জগতে integer division নিয়ম মানে না। inverse দিয়ে গুণ করতে হবে।
- **প্রতি inverse আলাদা Fermat-এ** — N টা `pow(..., p-2, p)` call করলে O(N log p), ধীর। একটা Fermat + পেছন-থেকে-গুণ যথেষ্ট (O(N))।
- **`r > n` / `r < 0` না ধরা** — তখন C = 0; না ধরলে array index error বা ভুল মান।
- **non-prime mod-এ এই pipeline** — Fermat inverse শুধু prime p-তে। mod prime না হলে Lucas theorem বা অন্য কৌশল লাগে।
- **`N ≥ p` রাখা (সূক্ষ্ম ফাঁদ)** — `i ≥ p` হলে `fact[i] = i! ≡ 0 (mod p)` (কারণ গুণফলে `p` ঢোকে), আর 0-এর inverse নেই — পুরো inv_fact শূন্য হয়ে যায়! বাস্তবে `p = 10⁹+7` বিশাল বলে `n` কখনো `p` ছোঁয় না, তাই সমস্যা হয় না; কিন্তু ছোট prime দিয়ে test করলে অবশ্যই `N < p` রাখো। (n ≥ p হলে Lucas theorem লাগে।)
- **`fact[0]` ভুল** — `0! = 1`; array `[1] * (N+1)` দিয়ে শুরু করায় ঠিক থাকে, কিন্তু খেয়াল রাখো।
- **inv_fact-এর পেছন-থেকে দিক উল্টানো** — `inv_fact[i-1] = inv_fact[i] * i`, `inv_fact[i+1] * ...` নয়; দিক উল্টালে সব ভুল।
- **N ছোট রেখে বড় n query** — precompute N অন্তত সবচেয়ে বড় n পর্যন্ত হতে হবে; নাহলে index out of range।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Binomial Coefficients** (