132 — Fibonacci using Matrix Exponentiation¶
131-এ matrix exponentiation-এর সাধারণ ছাঁচ শিখলে; এই note-এ সেটার সবচেয়ে বিখ্যাত খদ্দের — Fibonacci-র n-তম পদ O(log n)-এ। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — তবে "Fibonacci-র বিশাল n-তম পদ" CP-তে নিত্য, আর fast Fibonacci interview-তেও মাঝে মাঝে ওঠে। 131 ভালো বুঝে থাকলে এটা প্রায় সরাসরি প্রয়োগ।
Source¶
- Original source: CP-Algorithms — Fibonacci Numbers
- Platform: CP-Algorithms — https://cp-algorithms.com/algebra/fibonacci-numbers.html
- Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
- Difficulty: Hard
- Pattern: matrix power
- Basic idea inherited from: 131 (Matrix Exponentiation)
1. Problem in simple words¶
Fibonacci সংখ্যা — যেখানে প্রতিটা পদ আগের দুটোর যোগফল:
প্রশ্ন: 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" চিন্তাটা একবার দেখলে অনেক জায়গায় কাজে লাগে।
2. What is the math idea?¶
মূল idea — Fibonacci recurrence একটা 2×2 matrix গুণে এক ধাপ এগোয়:
মানে [[1,1],[1,0]] দিয়ে একবার গুণ = এক ধাপ Fibonacci এগোনো। তাই n বার এগোনো = সেই matrix-এর n-তম ঘাত:
আর [[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 গুণে বদলে দ্রুত ঘাত।
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।
4. Real-life analogy¶
ভাবো একটা খরগোশের জোড়া প্রতি মাসে নতুন জোড়া জন্ম দেয় (Fibonacci-র আদি গল্প)। প্রতি মাসে মোট জোড়ার সংখ্যা একটা নিয়মে বাড়ে — এই মাসের সংখ্যা = গত মাস + তার আগের মাস।
এখন তুমি জানতে চাও 1000তম মাসে কত জোড়া — কিন্তু মাস-by-মাস 999 বার হিসাব করা ক্লান্তিকর। matrix হলো "এক মাস এগোনোর নিয়ম"-টা গণিতে ধরা; আর matrix exponentiation হলো — "1 মাসের নিয়ম"-কে বর্গ করে "2 মাস", "4 মাস", "8 মাস"-এর নিয়ম বানিয়ে, মাত্র গুটিকয় বড় লাফে 1000 মাস পৌঁছে যাওয়া।
ঠিক যেমন 131-এ "n ধাপ সিঁড়ি" এক লাফে উঠেছিলাম — এখানে "n মাস Fibonacci" এক লাফে।
5. Visual explanation¶
কেন [[1,1],[1,0]] কাজ করে — এক ধাপ গুণ করে দেখি:
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)।
6. Example input and output¶
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)-ও বিশাল হলেও সঠিক বের হয়।
7. Brute force thinking¶
সরলতম — iterative loop, দুটো variable রেখে এগোনো (এটাই সবচেয়ে স্বাভাবিক Fibonacci):
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 বিশাল:
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)। ধাপ:
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 হলো সেই ছাঁচের পোস্টার-বয়।
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-এ যাচাই করা আছে।)
12. Python solution¶
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¶
2×2 matrix গুণ সরাসরি চারটা ঘরে লেখা (loop ছাড়া, একটু দ্রুত) — প্রতিটা ঘর ∑ A[i][k]·B[k][j]। mod দিলে চারটাতেই % mod।
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!।
14. Output walkthrough¶
চালালে যা ছাপবে:
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!।
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¶
- ভুল ঘর থেকে F(n) পড়া —
M^n-এ F(n) আছে top-right (R[0][1]) বা bottom-left (R[1][0]); top-left হলো F(n+1)। ঘর গুলিয়ে ফেললে এক পদ এদিক-ওদিক। - base case (0, 1) না সামলানো — n = 0-এ matrix power ডাকলে M^0 = identity, যার top-right 0 — যা আসলে F(0)-র সাথে মেলে, কিন্তু পরিষ্কার রাখতে আলাদা সামলানো ভালো।
- matrix গুণের order/সংজ্ঞা ভুল — 131-এর মতোই; matrix গুণ commutative নয়, ঘর-হিসাব নির্ভুল রাখো।
- mod ভেতরে না দেওয়া — বড় n-এ mod ছাড়া (C++/Java-তে) overflow; Python-এ overflow নেই কিন্তু সংখ্যা বিশাল হয়ে ধীর হয়। CP-তে mat_mult-এর ভেতরে
% mod। - ছোট n-এও matrix ব্যবহার করে over-engineer — n ছোট হলে iterative O(n)-ই সহজ; matrix-এর আসল মূল্য বিশাল n-এ। তবে শেখার জন্য দুটোই জানা ভালো।
18. Harder problems that inherit this idea¶
- CSES — Fibonacci Numbers (https://cses.fi/problemset/task/1722) — সরাসরি বিশাল n-এ F(n) mod, matrix exponentiation-এর classic।
- Codeforces — generalized linear recurrence problems (https://codeforces.com/problemset) — Fibonacci-র চেয়ে বড় recurrence (tribonacci ইত্যাদি) একই matrix-চিন্তায়।
- 133 (Fast Doubling Fibonacci) — এই repo-রই পরের ধাপ; Fibonacci-র জন্য matrix-এরও shortcut। আর Level 11-এর graph-path power (147) একই matrix-power-এ দাঁড়ায়।
19. Pattern learned¶
Fibonacci via matrix power — [[1,1],[1,0]]^n-এর top-right ঘর = F(n); binary exponentiation-এ O(log n)। বড় শিক্ষা: যোগের recurrence-কে "এক ধাপ এগোনোর matrix"-এ ভরে দিলে, n ধাপ = সেই matrix-এর n-তম ঘাত — আর ঘাত মানেই দ্রুত binary exponentiation। Fibonacci এই চিন্তার সবচেয়ে পরিষ্কার উদাহরণ।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "F(n) = [[1,1],[1,0]]^n-এর top-right; matrix expo-তে O(log n); base 0, 1 আলাদা; বড় n-এ mod ভেতরে।" Signal: "Fibonacci-র (বা যেকোনো linear recurrence-এর) বিশাল n-তম পদ" — দেখলেই এই matrix-power pattern মনে পড়বে।
পরের ধাপ → 133 — Fast Doubling Fibonacci (Fibonacci-র জন্য matrix-এরও shortcut)। ভিত্তি → 131 — Matrix Exponentiation।
ফিরে দেখা: এই 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" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।