034 — nCr mod Prime

এটা এই level-এর শিখর (Hard)। ভয় পেও না — আগের সব problem ঠিকঠাক করলে এটা আপনিই দাঁড়িয়ে যাবে, কারণ এটা নতুন কোনো জাদু নয়, বরং চেনা তিনটে অস্ত্রের জোট: factorial-mod (028), Fermat inverse (032), আর প্রতি step-এ mod। ধীরে পড়ো; pipeline-টা ধাপে ধাপে গড়ব।

Source

• Original source: CP-Algorithms — Binomial Coefficients
• Platform: CP-Algorithms — https://cp-algorithms.com/combinatorics/binomial-coefficients.html
• 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)

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 চাই।

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 দিয়ে গুণ; এটাই পুরো গল্প।

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-এর জোট — তাই আলাদা করে কঠিন কিছু নয়, শুধু একসাথে সাজানো।

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-এর পুরো দর্শন এটাই: একবার খাটো, বারবার সুফল।

5. Visual explanation

C(5, 2) mod 7 — সংজ্ঞা থেকে pipeline:

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):

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   ✓ মিলল!

6. Example input and output

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 হয়ে আছে।

7. Brute force thinking

সরল (Python-এই): সরাসরি সংজ্ঞা — factorial বানিয়ে integer ভাগ, তারপর mod। অথবা mod-জগতে প্রতি query-তে নতুন করে factorial + Fermat inverse।

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⁶ হলে অসম্ভব।

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):

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-র তফাত।

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):

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 ✓।)

12. Python solution

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

    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 (খালি গুণফল)।

    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।

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।

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!।

14. Output walkthrough

চালালে যা ছাপবে:

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!।

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।

18. Harder problems that inherit this idea

• CSES — Binomial Coefficients (https://cses.fi/problemset/task/1079) — হুবহু এই pipeline; অনেক query।
• CSES — Distributing Apples / Christmas Party ধরনের counting — nCr mod p-কে building block হিসেবে ব্যবহার করে।
• Lucas' theorem problems — n বিশাল কিন্তু p ছোট prime হলে nCr mod p; এই pipeline-এর সম্প্রসারণ (CP-Algorithms binomial page-এ আছে)।

19. Pattern learned

nCr mod p pipeline — factorial precompute (fact[i] = fact[i−1]×i % p) + inverse factorial (একটা Fermat তারপর inv_fact[i−1] = inv_fact[i]×i % p) + query fact[n] × inv_fact[r] × inv_fact[n−r] % p। ভাগ → inverse গুণ; একবার O(N) prep, query O(1)। mod prime চাই।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "nCr mod p = fact[] + inv_fact[] precompute (inv_fact শেষেরটা Fermat, বাকি পেছন থেকে গুণে), query = fact[n]×inv_fact[r]×inv_fact[n−r]। ভাগ নেই — inverse দিয়ে গুণ। 'বড় n, অনেক query, mod prime' দেখলেই এই pipeline।"

পরের ধাপ → 035 — Modular Division (inverse দিয়ে ভাগের সাধারণ রূপ)। সম্পর্কিত → 032 — Modular Inverse Basic, 033 — Fermat Little Theorem।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।