Problem link ও উৎস
- **Original source:** CP-Algorithms — Fibonacci Numbers
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** matrix power
- **Basic idea inherited from:** 131 (Matrix Exponentiation)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
Fibonacci সংখ্যা — যেখানে প্রতিটা পদ আগের দুটোর যোগফল:
```
F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2)
ধারা: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
```
প্রশ্ন: **n-তম Fibonacci সংখ্যা F(n) দ্রুত বের করা** — n যখন বিশাল (যেমন 10¹⁸), সাধারণত mod কোনো বড় সংখ্যায় (যেমন 10⁹+7)।
সরল loop-এ F(n) বের করতে n ধাপ লাগে — n = 10¹⁸ হলে অসম্ভব। লক্ষ্য — 131-এর matrix exponentiation দিয়ে এটা **O(log n)**-এ নামানো। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু "recurrence → matrix → fast power" চিন্তাটা একবার দেখলে অনেক জায়গায় কাজে লাগে।
### Input ও output {#6-example-input-and-output}
```text
input n -> F(n) পদ্ধতি
----------------------------------------------------------------
0 -> 0 base
1 -> 1 base
10 -> 55 M^10-এর top-right
20 -> 6765
50 -> 12586269025
100 -> 354224848179261915075 (Python big int, mod ছাড়া)
mod সহ (CP-style), mod = 10⁹+7:
F(100) mod (10⁹+7) -> 687995182
F(10¹⁸) mod (10⁹+7) -> (বিশাল n, তবু O(log n)-এ — কয়েক microsecond)
```
খেয়াল করো: **F(0) = 0, F(1) = 1** — দুটো base case আলাদা করে সামলানো ভালো (matrix M^0 = identity-র top-right 0, যা F(0)-র সাথে মেলে)। বড় n-এ mod নিয়ে কাজ করি; Python big int-এ mod ছাড়া F(100)-ও বিশাল হলেও সঠিক বের হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা খরগোশের জোড়া প্রতি মাসে নতুন জোড়া জন্ম দেয় (Fibonacci-র আদি গল্প)। প্রতি মাসে মোট জোড়ার সংখ্যা একটা নিয়মে বাড়ে — এই মাসের সংখ্যা = গত মাস + তার আগের মাস।
এখন তুমি জানতে চাও **1000তম মাসে কত জোড়া** — কিন্তু মাস-by-মাস 999 বার হিসাব করা ক্লান্তিকর। matrix হলো "এক মাস এগোনোর নিয়ম"-টা গণিতে ধরা; আর matrix exponentiation হলো — "1 মাসের নিয়ম"-কে বর্গ করে "2 মাস", "4 মাস", "8 মাস"-এর নিয়ম বানিয়ে, মাত্র গুটিকয় বড় লাফে 1000 মাস পৌঁছে যাওয়া।
ঠিক যেমন 131-এ "n ধাপ সিঁড়ি" এক লাফে উঠেছিলাম — এখানে "n মাস Fibonacci" এক লাফে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **131 (Matrix Exponentiation)**। 131-এর `mat_pow` (binary exponentiation on matrix) এখানে হুবহু ব্যবহার হয় — শুধু matrix-টা নির্দিষ্ট: `[[1,1],[1,0]]`। 131 না বুঝলে এর fast power বোঝা যায় না।
পেছনে আরও দাঁড়িয়ে আছে 029 (binary exponentiation)-এর চিন্তা। আর এর উপরে দাঁড়াবে **133 (Fast Doubling)** — Fibonacci-র জন্য matrix-এরও shortcut (matrix identity খুলে সরাসরি formula)। README-র recommended order-এ তাই 131 → 132 → 133 trilogy।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **Fibonacci recurrence একটা 2×2 matrix গুণে এক ধাপ এগোয়**:
```
[F(n+1)] [1 1] [F(n) ]
[F(n) ] = [1 0] [F(n−1)]
```
মানে `[[1,1],[1,0]]` দিয়ে একবার গুণ = এক ধাপ Fibonacci এগোনো। তাই n বার এগোনো = সেই matrix-এর n-তম ঘাত:
```
[F(n+1)] [1 1]^n [F(1)] [1 1]^n [1]
[F(n) ] = [1 0] [F(0)] = [1 0] [0]
```
আর `[[1,1],[1,0]]^n` বের করতে আমরা 131-এর binary exponentiation (O(log n)) ব্যবহার করি। সুন্দর একটা fact: `[[1,1],[1,0]]^n = [[F(n+1), F(n)], [F(n), F(n−1)]]` — মানে matrix-এর ঘরেই Fibonacci সংখ্যা বসে থাকে! এই level CP-leaning হলেও মূল সুর সরল — যোগের recurrence-কে matrix গুণে বদলে দ্রুত ঘাত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরলতম — **iterative loop, দুটো variable রেখে এগোনো** (এটাই সবচেয়ে স্বাভাবিক Fibonacci):
```python
def fib_iter(n, mod=None):
a, b = 0, 1 # F(0), F(1)
for _ in range(n):
a, b = b, a + b
if mod is not None:
a %= mod
b %= mod
return a # n বার পর a = F(n)
```
ছোট ও মাঝারি n-এ (যেমন 50, এমনকি 10⁶) এটা নিখুঁত ও দ্রুত — O(n)। আমাদের matrix version-এর উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য পরিষ্কার ও নির্ভরযোগ্য।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে ঠিক `n` বার। n যদি 10⁶ হয় — ঠিক আছে (মুহূর্ত)। কিন্তু CP-তে প্রায়ই n বিশাল:
```text
n = 10⁶: 10⁶ ধাপ — তাৎক্ষণিক, ঠিক আছে
n = 10¹⁸: 10¹⁸ ধাপ — অসম্ভব (কোটি কোটি বছর)
matrix exponentiation: ~log₂(n) ≈ 60 ধাপ — n=10¹⁸-এও microsecond
```
যখন n এত বড় যে একটা একটা করে এগোনো অসম্ভব (10¹⁸-তম পদ), তখন O(n) loop অচল। matrix exponentiation O(log n)-এ সেটা দেয় — এটাই বড় n-এর জন্য একমাত্র পথ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **Fibonacci recurrence matrix M = [[1,1],[1,0]]-এ ভরে দাও, তখন n ধাপ = M^n, যা binary exponentiation-এ O(log n)।** ধাপ:
```text
1. base: n == 0 -> 0, n == 1 -> 1 (আলাদা সামলাও, পরিষ্কার থাকে)
2. M = [[1,1],[1,0]]
3. R = mat_pow(M, n, mod) [131-এর binary exponentiation]
4. F(n) = R[0][1] (top-right ঘর = F(n))
```
কেন top-right: `M^n = [[F(n+1), F(n)], [F(n), F(n−1)]]`, তাই R[0][1] = F(n)। (চাইলে R[1][0]-ও একই F(n)।)
mod লাগলে mat_pow-এর ভেতরে প্রতিটা গুণ-যোগে `% mod` — তাহলে সংখ্যা ছোট থাকে, CP-র mod 10⁹+7-এ নিরাপদ।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **"দুটো যোগ করে এক ঘর এগোও" — এই গোটা recurrence একটামাত্র 2×2 matrix-এ ধরা যায়, তখন n ধাপ মানে সেই matrix-এর n-তম ঘাত।**
brute force n বার একে একে যোগ করছিল; tweak হলো — যোগের নিয়মটাকে matrix বানিয়ে, n-তম ঘাত binary exponentiation-এ নাও। O(n) থেকে O(log n)-এ নেমে এল। এটাই 131-এর সাধারণ ছাঁচের সবচেয়ে পরিষ্কার উদাহরণ — Fibonacci হলো সেই ছাঁচের পোস্টার-বয়।
### ছবিতে বোঝা {#5-visual-explanation}
কেন `[[1,1],[1,0]]` কাজ করে — এক ধাপ গুণ করে দেখি:
```text
matrix: M = [1 1]
[1 0]
এক ধাপ: M · [F(n) ] = [1·F(n) + 1·F(n−1)] [F(n) + F(n−1)] [F(n+1)]
[F(n−1)] [1·F(n) + 0·F(n−1)] = [F(n) ] = [F(n) ]
▲ যোগ করল, এক ঘর সরাল
তাই M^n · [F(1), F(0)]ᵀ = M^n · [1, 0]ᵀ = [F(n+1), F(n)]ᵀ
আর গোটা matrix-এর ঘাত:
M^1 = [[1,1],[1,0]] = [[F(2),F(1)],[F(1),F(0)]] = [[1,1],[1,0]] ✓
M^2 = [[2,1],[1,1]] = [[F(3),F(2)],[F(2),F(1)]] ✓
M^5 = [[8,5],[5,3]] = [[F(6),F(5)],[F(5),F(4)]] ✓
▲ top-right = F(5) = 5
```
লক্ষ করো — matrix-টা শুধু "দুটো যোগ করে এক ঘর সরাও" নিয়মটা ধরে রেখেছে। তাই n-তম ঘাতের top-right ঘরেই বসে থাকে F(n)।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`fib(10)` matrix দিয়ে — M = [[1,1],[1,0]], n = 10 = 1010 (binary):
| step | n (binary) | n & 1 | R (শুরু identity) | M (square) |
| --- | --- | --- | --- | --- |
| শুরু | 1010 | — | [[1,0],[0,1]] | [[1,1],[1,0]] |
| 1 | 1010 | 0 | R অপরিবর্তিত | M = M² = [[2,1],[1,1]] |
| 2 | 101 | 1 | R = R·M² = [[2,1],[1,1]] | M = M⁴ = [[5,3],[3,2]] |
| 3 | 10 | 0 | R অপরিবর্তিত | M = M⁸ = [[34,21],[21,13]] |
| 4 | 1 | 1 | R = R·M⁸ = [[55,34],[34,21]] | (n=0, শেষ) |
চূড়ান্ত R = [[55, 34], [34, 21]] = M^10। F(10) = R[0][1] = **34**? দাঁড়াও — R[0][1] = 34, কিন্তু F(10) = 55। আসলে R = M^10 = [[F(11), F(10)], [F(10), F(9)]] = [[89, 55], [55, 34]]...
দেখি ঠিকঠাক: M^10-এর top-left = F(11) = 89, top-right = F(10) = 55। উপরের শেষ ধাপে R = R·M⁸ যেখানে R ছিল M²(= M^2) আর M⁸, মানে R = M^(2+8) = M^10 = [[89,55],[55,34]]। তাই **F(10) = R[0][1] = 55** ✓। (উপরের table-এর শেষ সারিতে গুণফল হলো [[89,55],[55,34]] — code-এ যাচাই করা আছে।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mat_mult(A, B, mod=None):
"""2×2 matrix গুণ, mod দিলে % mod।"""
a = A[0][0] * B[0][0] + A[0][1] * B[1][0]
b = A[0][0] * B[0][1] + A[0][1] * B[1][1]
c = A[1][0] * B[0][0] + A[1][1] * B[1][0]
d = A[1][0] * B[0][1] + A[1][1] * B[1][1]
if mod is not None:
a, b, c, d = a % mod, b % mod, c % mod, d % mod
return [[a, b], [c, d]]
def mat_pow(M, power, mod=None):
"""M^power — binary exponentiation (131 থেকে)।"""
R = [[1, 0], [0, 1]] # identity
M = [row[:] for row in M]
while power > 0:
if power & 1:
R = mat_mult(R, M, mod)
M = mat_mult(M, M, mod)
power >>= 1
return R
def fib(n, mod=None):
"""n-তম Fibonacci — matrix exponentiation, O(log n)।"""
if n == 0:
return 0
if n == 1:
return 1 % mod if mod else 1
R = mat_pow([[1, 1], [1, 0]], n, mod)
return R[0][1] # top-right = F(n)
# --- ছোট test গুলো (সব pass করা উচিত) ---
def fib_iter(n, mod=None):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
if mod is not None:
a %= mod; b %= mod
return a
# matrix বনাম iterative — n = 0..40 সব মেলাও
for n in range(0, 41):
assert fib(n) == fib_iter(n), f"F({n}) অমিল"
# known মান
assert fib(0) == 0
assert fib(1) == 1
assert fib(10) == 55
assert fib(20) == 6765
assert fib(50) == 12586269025
assert fib(100) == 354224848179261915075
# matrix-এর গঠন যাচাই: M^n = [[F(n+1), F(n)], [F(n), F(n−1)]]
for n in range(1, 20):
R = mat_pow([[1, 1], [1, 0]], n)
assert R[0][0] == fib_iter(n + 1)
assert R[0][1] == fib_iter(n)
assert R[1][0] == fib_iter(n)
assert R[1][1] == fib_iter(n - 1)
# mod সহ — বড় n-এও দ্রুত ও সঠিক
MOD = 10**9 + 7
for n in range(0, 200):
assert fib(n, MOD) == fib_iter(n, MOD), f"mod F({n}) অমিল"
assert fib(10**18, MOD) == fib(10**18, MOD) # বিশাল n চলে (O(log n))
print(fib(10)) # 55
print(fib(100)) # 354224848179261915075
print(fib(10**18, MOD)) # বড় n mod — তাৎক্ষণিক
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def mat_mult(A, B, mod=None):
a = A[0][0]*B[0][0] + A[0][1]*B[1][0]
...
```
2×2 matrix গুণ সরাসরি চারটা ঘরে লেখা (loop ছাড়া, একটু দ্রুত) — প্রতিটা ঘর `∑ A[i][k]·B[k][j]`। mod দিলে চারটাতেই `% mod`।
```
def mat_pow(M, power, mod=None):
R = [[1, 0], [0, 1]]
...
```
131-এর binary exponentiation-এর হুবহু 2×2 রূপ — R identity থেকে শুরু, power-এর bit ধরে R·=M, প্রতি ধাপে M square।
```
def fib(n, mod=None):
if n == 0: return 0
if n == 1: return 1 % mod if mod else 1
R = mat_pow([[1, 1], [1, 0]], n, mod)
return R[0][1]
```
base case (0, 1) আলাদা — পরিষ্কার ও নিরাপদ। নাহলে Fibonacci matrix-এর n-তম ঘাত নিয়ে top-right ঘর (R[0][1] = F(n)) ফেরত। mod থাকলে F(1)-এও `% mod` (যদিও 1 < সব বাস্তব mod, তবু সঙ্গতির জন্য)।
বাকি test অংশে matrix বনাম iterative (n = 0..40), known মান, matrix-এর গঠন (`M^n`-এর চার ঘর), আর mod সহ (এমনকি n = 10¹⁸) সব যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
55
354224848179261915075
<একটা বড় সংখ্যা, যেমন 209783453 জাতীয়>
সব test pass!
```
`fib(10)` → 55 (M^10-এর top-right)। `fib(100)` → পুরো 21-অঙ্কের Fibonacci (Python big int, mod ছাড়া সঠিক)। `fib(10**18, MOD)` → 10¹⁸-তম Fibonacci mod 10⁹+7 — একটা 9-অঙ্কের সংখ্যা, আর এটা **তাৎক্ষণিক** কারণ matrix exponentiation মাত্র ~60 ধাপ। তার আগে শত শত assert (matrix vs iterative, গঠন, mod) pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — Fibonacci matrix 2×2 (ধ্রুব আকার), তাই প্রতিটা matrix গুণ O(1), আর binary exponentiation ~log₂n বার গুণ করে। তাই n = 10¹⁸-এও মাত্র ~60 matrix গুণ — microsecond-এর ব্যাপার। iterative loop-এর O(n)-এর তুলনায় বিশাল লাফ (বড় n-এ)। (ছোট n-এ অবশ্য iterative-ই সহজ ও যথেষ্ট।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — মাত্র গুটিকয় 2×2 matrix (R, M, temporary), আকার ধ্রুব। recursion নেই (iterative power), তাই extra stack নেই। ঘাত n যত বড়ই হোক memory বাড়ে না। (mod ছাড়া বিশাল n-এ Fibonacci সংখ্যা নিজেই বিশাল হয়, তখন big-int-এর digit-সংখ্যার সাথে space বাড়ে — তাই CP-তে mod নেওয়া হয়।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **ভুল ঘর থেকে F(n) পড়া** — `M^n`-এ F(n) আছে top-right (R[0][1]) বা bottom-left (R[1][0]); top-left হলো F(n+1)। ঘর গুলিয়ে ফেললে এক পদ এদিক-ওদিক।
2. **base case (0, 1) না সামলানো** — n = 0-এ matrix power ডাকলে M^0 = identity, যার top-right 0 — যা আসলে F(0)-র সাথে মেলে, কিন্তু পরিষ্কার রাখতে আলাদা সামলানো ভালো।
3. **matrix গুণের order/সংজ্ঞা ভুল** — 131-এর মতোই; matrix গুণ commutative নয়, ঘর-হিসাব নির্ভুল রাখো।
4. **mod ভেতরে না দেওয়া** — বড় n-এ mod ছাড়া (C++/Java-তে) overflow; Python-এ overflow নেই কিন্তু সংখ্যা বিশাল হয়ে ধীর হয়। CP-তে mat_mult-এর ভেতরে `% mod`।
5. **ছোট n-এও matrix ব্যবহার করে over-engineer** — n ছোট হলে iterative O(n)-ই সহজ; matrix-এর আসল মূল্য বিশাল n-এ। তবে শেখার জন্য দুটোই জানা ভালো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Fibonacci Numbers** (