Problem link ও উৎস
- **Original source:** CP-Algorithms — Fibonacci Numbers (Fast Doubling section)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** F(2k) formulas
- **Basic idea inherited from:** 132 (Fibonacci using Matrix Exponentiation)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
আগের মতোই — **n-তম Fibonacci সংখ্যা F(n) দ্রুত বের করা** (n বিশাল, প্রায়ই mod কোনো বড় সংখ্যায়)। কিন্তু এবার একটা আরও চটপটে পদ্ধতি: **fast doubling**।
মূল চাবি দুটো সুন্দর সূত্র, যা k থেকে সরাসরি 2k-তে লাফ দেয়:
```
F(2k) = F(k) · (2·F(k+1) − F(k))
F(2k+1) = F(k)² + F(k+1)²
```
মানে F(k) আর F(k+1) জানলে, এক ধাপে F(2k) আর F(2k+1) পেয়ে যাও। n-এর binary bit ধরে ধরে এই doubling করলে O(log n)-এ F(n) — কিন্তু matrix-এর চেয়ে কম গুণে। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু এই doubling-চিন্তা গণিতগতভাবে দারুণ।
### Input ও output {#6-example-input-and-output}
```text
input n -> F(n) পদ্ধতি
----------------------------------------------------------------
0 -> 0 base
1 -> 1 base
10 -> 55 fast doubling
20 -> 6765
50 -> 12586269025
100 -> 354224848179261915075 (Python big int)
mod সহ (CP-style), mod = 10⁹+7:
F(100) mod (10⁹+7) -> 687995182
F(10¹⁸) mod (10⁹+7) -> তাৎক্ষণিক (O(log n), matrix-এর চেয়েও কম গুণ)
```
খেয়াল করো: উত্তর 132-এর সাথে হুবহু এক (একই Fibonacci!) — শুধু পদ্ধতি দ্রুততর। **base case F(0) = 0, F(1) = 1** এখানেও; recursion-এর তলানিতে `n == 0` হলে (F(0), F(1)) = (0, 1) ফেরত। বড় n-এ mod, Python big int-এ mod ছাড়াও সঠিক।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা লম্বা সিঁড়ির n-তম ধাপে পৌঁছাতে চাও, কিন্তু তোমার একটা বিশেষ ক্ষমতা আছে — **যেখানে আছো তার দ্বিগুণে এক লাফে যেতে পারো** (k → 2k), আর চাইলে একটা মাত্র ধাপ এগোতে পারো (k → k+1)।
তাহলে n-এ পৌঁছানোর চটপটে উপায়: n-কে binary-তে ভাবো। MSB থেকে শুরু করে, প্রতিটা bit-এ "দ্বিগুণ লাফ" দাও; bit যদি 1 হয়, সেই সাথে "এক ধাপ" বাড়াও। যেমন n = 13 = 1101: শুরু 0 → 1 → 11 → 110 → 1101, প্রতি ধাপে দ্বিগুণ + (bit 1 হলে) এক বাড়তি।
fast doubling ঠিক এই — "যেখানে আছি (F(k), F(k+1)) সেখান থেকে দ্বিগুণে লাফ" — matrix-এর মতো ঘুরপথ নয়, সরাসরি দুটো সূত্রে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **132 (Fibonacci using Matrix Exponentiation)**। fast doubling-এর দুটো সূত্রই `M^(2k) = (M^k)²` থেকে বেরোয় — মানে 132-এর matrix-চিন্তা না বুঝলে এই formula-র উৎস বোঝা যায় না। fast doubling হলো সেই matrix squaring-এর optimized, scalar রূপ।
পেছনে আরও দাঁড়িয়ে আছে 131 (matrix exponentiation) আর 029 (binary exponentiation)-এর "binary bit ধরে এগোনো" চিন্তা। README-র recommended order-এ 131 → 132 → 133 — এটাই trilogy-র শেষ ও সবচেয়ে পরিমার্জিত ধাপ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **matrix identity `[[1,1],[1,0]]^n`-এর ঘরগুলো খুলে লিখলেই doubling formula বেরিয়ে আসে।** 132-এ দেখেছিলে:
```
M^n = [[F(n+1), F(n)], [F(n), F(n−1)]]
```
এখন `M^(2k) = (M^k)²`। ডান পাশের বর্গটা ঘরে ঘরে গুণ করে, F(2k) আর F(2k+1)-কে F(k), F(k+1)-এর ভাষায় লিখলেই উপরের দুই সূত্র। তাই fast doubling আসলে matrix squaring-এরই হাতে-লেখা, পরিষ্কার রূপ — matrix-এর 8টা গুণের বদলে মাত্র 3টা গুণ লাগে। n-কে binary-তে (MSB থেকে) পড়ে প্রতিটা bit-এ একবার doubling, bit 1 হলে এক ধাপ বাড়তি সরানো। এই level CP-leaning হলেও মূল সুর সরল — k জানলে 2k এক লাফে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
আগের মতোই — সরল iterative loop (এটাই reference হিসেবে রাখব মিলিয়ে দেখতে):
```python
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
```
ছোট ও মাঝারি n-এ নিখুঁত ও সহজ — O(n)। fast doubling-এর প্রতিটা উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। নির্ভরযোগ্য ভিত্তি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে n বার — n = 10⁶ হলে ঠিক আছে, কিন্তু বিশাল n-এ অচল:
```text
n = 10⁶: 10⁶ ধাপ — তাৎক্ষণিক
n = 10¹⁸: 10¹⁸ ধাপ — অসম্ভব
matrix expo (132): ~log n matrix গুণ (প্রতিটায় 8 scalar গুণ)
fast doubling (133): ~log n ধাপ, প্রতি ধাপে মাত্র 3 scalar গুণ ← সবচেয়ে কম
```
বড় n-এ O(n) অচল। আর matrix expo (132)-এর সাথে তুলনায়, fast doubling একই O(log n) কিন্তু প্রতি ধাপে কম গুণ (matrix-এর 8টার বদলে 3টা) — তাই ধ্রুবক গুণনীয়ক ছোট, ব্যবহারিকভাবে দ্রুততর।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **F(k), F(k+1) জানলে দুই সূত্রে F(2k), F(2k+1) পাওয়া যায়; তাই n-এর binary bit ধরে doubling করলেই O(log n)।** recursive কাঠামো সবচেয়ে পরিষ্কার:
```text
fib_pair(n) -> (F(n), F(n+1)) ফেরত দেয়
base: n == 0 -> (0, 1)
নাহলে:
(a, b) = fib_pair(n >> 1) [a = F(k), b = F(k+1), যেখানে k = n//2]
c = a · (2·b − a) [F(2k)]
d = a² + b² [F(2k+1)]
যদি n বিজোড়: return (d, c + d) [F(2k+1), F(2k+2)]
নাহলে: return (c, d) [F(2k), F(2k+1)]
```
কেন: n//2 = k-এর pair থেকে 2k-এর pair বানাই (c, d)। n যদি জোড় (n = 2k), উত্তর (c, d); n বিজোড় (n = 2k+1), এক ধাপ সরিয়ে (d, c+d) — কারণ F(2k+2) = F(2k) + F(2k+1) = c + d। শেষে fib_pair(n)[0] = F(n)। mod লাগলে প্রতিটা গুণ-যোগে `% mod`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **matrix squaring-এর ঘরগুলো হাতে খুললে দুটো scalar formula বেরোয় — matrix-এর সব ঘর না রেখে শুধু F(k), F(k+1) বইলেই হয়।**
132-এ পুরো 2×2 matrix square করছিলাম (8 গুণ); tweak হলো — সেই বর্গের শুধু দরকারি দুই ঘর (F(2k), F(2k+1)) আলাদা সূত্রে লেখো, তখন প্রতি ধাপে মাত্র 3 গুণ। একই O(log n), কিন্তু ছোট ধ্রুবক — matrix থেকে scalar doubling-এ নেমে এল। গণিতই বলে দিল কোন ঘরগুলো আসলে লাগে।
### ছবিতে বোঝা {#5-visual-explanation}
doubling formula কোথা থেকে আসে — `(M^k)²` খুলে:
```text
M^k = [[F(k+1), F(k) ],
[F(k), F(k−1)]]
(M^k)² = M^(2k)-এর top-left আর top-right হিসাব করি:
top-right (= F(2k)):
F(k+1)·F(k) + F(k)·F(k−1)
= F(k)·(F(k+1) + F(k−1))
= F(k)·(F(k+1) + (F(k+1) − F(k))) [F(k−1) = F(k+1) − F(k)]
= F(k)·(2·F(k+1) − F(k)) ← সূত্র ১ ✓
top-left (= F(2k+1)):
F(k+1)² + F(k)² ← সূত্র ২ ✓
ছোট যাচাই (k = 3): F(3)=2, F(4)=3
F(6) = F(3)·(2·F(4) − F(3)) = 2·(6 − 2) = 8 ✓ (F(6) = 8)
F(7) = F(4)² + F(3)² = 9 + 4 = 13 ✓ (F(7) = 13)
```
লক্ষ করো — দুটো সূত্রই matrix বর্গের ঘর থেকে সোজা বেরোল, আর k = 3-এ হাতে মিলিয়ে F(6) = 8, F(7) = 13 পেলাম।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`fib_pair(10)` — recursion (n = 10):
| call | n | n >> 1 | কী ফেরে |
| --- | --- | --- | --- |
| 1 | 10 | 5 | fib_pair(5)-এর অপেক্ষা |
| 2 | 5 | 2 | fib_pair(2)-এর অপেক্ষা |
| 3 | 2 | 1 | fib_pair(1)-এর অপেক্ষা |
| 4 | 1 | 0 | fib_pair(0)-এর অপেক্ষা |
| 5 | 0 | — | base → return (0, 1) |
ফেরার পথ (a = F(k), b = F(k+1); c = F(2k), d = F(2k+1)):
| ফেরা | k | (a, b) | c = a(2b−a) | d = a²+b² | n বিজোড়? | return (F(n), F(n+1)) |
| --- | --- | --- | --- | --- | --- | --- |
| call 5→4 | 0 | (0, 1) | 0·(2−0)=0 | 0+1=1 | n=1 বিজোড় | (d, c+d) = (1, 1) |
| call 4→3 | 1 | (1, 1) | 1·(2−1)=1 | 1+1=2 | n=2 জোড় | (c, d) = (1, 2) |
| call 3→2 | 2 | (1, 2) | 1·(4−1)=3 | 1+4=5 | n=5 বিজোড় | (d, c+d) = (5, 8) |
| call 2→1 | 5 | (5, 8) | 5·(16−5)=55 | 25+64=89 | n=10 জোড় | (c, d) = (55, 89) |
চূড়ান্ত: fib_pair(10) = (55, 89), তাই **F(10) = 55** ✓ (আর F(11) = 89)। দেখো — প্রতি ধাপে শুধু দুটো সংখ্যা বইলাম, matrix নয়।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import sys
sys.setrecursionlimit(10000)
def fib_pair(n, mod=None):
"""(F(n), F(n+1)) ফেরত দেয় — fast doubling, O(log n)।"""
if n == 0:
return (0, 1)
a, b = fib_pair(n >> 1, mod) # a = F(k), b = F(k+1), k = n//2
c = a * (2 * b - a) # F(2k)
d = a * a + b * b # F(2k+1)
if mod is not None:
c %= mod
d %= mod
if n & 1: # n বিজোড় (n = 2k+1)
return (d, (c + d) % mod if mod else c + d)
else: # n জোড় (n = 2k)
return (c, d)
def fib(n, mod=None):
"""n-তম Fibonacci — fast doubling।"""
return fib_pair(n, mod)[0]
# --- ছোট 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
# fast doubling বনাম iterative — n = 0..60 সব মেলাও
for n in range(0, 61):
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
# pair-এর দুই ঘর সঠিক: (F(n), F(n+1))
for n in range(0, 30):
p = fib_pair(n)
assert p == (fib_iter(n), fib_iter(n + 1)), f"pair({n}) অমিল"
# doubling সূত্র সরাসরি যাচাই: F(2k) ও F(2k+1)
for k in range(0, 30):
assert fib_iter(2 * k) == fib_iter(k) * (2 * fib_iter(k + 1) - fib_iter(k))
assert fib_iter(2 * k + 1) == fib_iter(k) ** 2 + fib_iter(k + 1) ** 2
# mod সহ — বড় n-এও দ্রুত ও সঠিক
MOD = 10**9 + 7
for n in range(0, 300):
assert fib(n, MOD) == fib_iter(n, MOD), f"mod F({n}) অমিল"
assert fib(10**18, MOD) >= 0 # বিশাল n চলে (O(log n))
# 132-এর matrix পদ্ধতির সাথেও একই উত্তর (cross-check)
def fib_matrix(n, mod=None):
def mm(A, B):
x = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
s = A[i][0] * B[0][j] + A[i][1] * B[1][j]
x[i][j] = s % mod if mod else s
return x
R, M, p = [[1, 0], [0, 1]], [[1, 1], [1, 0]], n
while p:
if p & 1: R = mm(R, M)
M = mm(M, M); p >>= 1
return R[0][1]
for n in range(0, 100):
assert fib(n, MOD) == fib_matrix(n, MOD)
print(fib(10)) # 55
print(fib(100)) # 354224848179261915075
print(fib(10**18, MOD)) # বড় n mod — তাৎক্ষণিক
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def fib_pair(n, mod=None):
if n == 0:
return (0, 1)
```
recursion-এর তলানি — F(0) = 0, F(1) = 1, তাই (0, 1)। এই pair থেকে উপরে উঠতে উঠতে বড় index বানাব।
```
a, b = fib_pair(n >> 1, mod)
c = a * (2 * b - a)
d = a * a + b * b
```
আগে অর্ধেক index k = n//2-এর pair (a = F(k), b = F(k+1)) আনি। তারপর section 5-এর দুই সূত্রে c = F(2k), d = F(2k+1) — মাত্র 3টা গুণ (a·(...), a·a, b·b)। mod থাকলে c, d-তে `% mod`।
```
if n & 1:
return (d, (c + d) % mod if mod else c + d)
else:
return (c, d)
```
n যদি জোড় (n = 2k) — উত্তর (F(2k), F(2k+1)) = (c, d)। n বিজোড় (n = 2k+1) — এক ধাপ সরিয়ে (F(2k+1), F(2k+2)) = (d, c+d), কারণ F(2k+2) = F(2k) + F(2k+1)।
```
def fib(n, mod=None):
return fib_pair(n, mod)[0]
```
pair-এর প্রথম ঘরই F(n)।
বাকি test অংশে fast doubling বনাম iterative (n = 0..60), pair-এর দুই ঘর, doubling সূত্র সরাসরি, mod, আর 132-এর matrix পদ্ধতির সাথে cross-check — সব যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
55
354224848179261915075
<একটা বড় ৯-অঙ্কের সংখ্যা>
সব test pass!
```
`fib(10)` → 55 (section 11-এর dry run-এর সাথে মিল)। `fib(100)` → পুরো 21-অঙ্কের Fibonacci (Python big int)। `fib(10**18, MOD)` → 10¹⁸-তম Fibonacci mod 10⁹+7, **তাৎক্ষণিক** (O(log n), matrix-এর চেয়েও কম গুণ)। তার আগে সব assert (iterative, pair, doubling সূত্র, mod, matrix cross-check) pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — recursion-এর গভীরতা ~log₂n (প্রতি ধাপে n অর্ধেক), আর প্রতি ধাপে ধ্রুবক কাজ (মাত্র 3টা গুণ + কয়েকটা যোগ)। matrix exponentiation (132)-ও O(log n), কিন্তু fast doubling-এ প্রতি ধাপে কম scalar গুণ (3 বনাম matrix-এর 8), তাই ধ্রুবক গুণনীয়ক ছোট — ব্যবহারিকভাবে দ্রুততম Fibonacci পদ্ধতিগুলোর একটা।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log n)** — recursion-এর call stack-এর গভীরতা ~log₂n। চাইলে iterative (n-এর bit MSB থেকে পড়ে) লিখে **O(1)**-এ নামানো যায়। প্রতিটা frame-এ শুধু কয়েকটা সংখ্যা (a, b, c, d) — কোনো array নেই। (mod ছাড়া বিশাল n-এ Fibonacci সংখ্যা নিজেই বড়, big-int digit-এর সাথে space বাড়ে — তাই CP-তে mod।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **জোড়/বিজোড় শাখা গুলিয়ে ফেলা** — n জোড় হলে (c, d), বিজোড় হলে (d, c+d)। উল্টে ফেললে এক পদ এদিক-ওদিক, পুরো উত্তর ভুল। `n & 1` দিয়ে সঠিক শাখা।
2. **`2·F(k+1) − F(k)` negative হওয়া (mod-এ)** — mod নিয়ে কাজ করলে `2*b − a` negative হতে পারে; তখন `c %= mod`-এর পর Python ঠিক রাখে, কিন্তু C++/Java-তে `((2*b − a) % mod + mod) % mod` লাগে।
3. **base case ভুল** — `n == 0` হলে (0, 1) ফেরত (F(0), F(1)); (1, 1) বা (1, 0) দিলে সব ভুল।
4. **fib_pair-এর কোন ঘর F(n) ভুলে যাওয়া** — F(n) হলো pair-এর **প্রথম** ঘর ([0]), দ্বিতীয়টা F(n+1)।
5. **recursion limit/গভীরতা (বিশাল n)** — n = 10¹⁸-এ গভীরতা ~60, তাই নিরাপদ; কিন্তু খুব রক্ষণশীল default limit-এ চাইলে iterative version বা `setrecursionlimit`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Fibonacci Numbers** (