Problem link ও উৎস
- **Original source:** Classic CP technique (USACO Guide)
- **Platform:** USACO Guide —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** recurrence as matrix
- **Basic idea inherited from:** 029 (Binary Exponentiation)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো বর্গাকার (square) matrix গুণ করা যায়। প্রশ্ন: একটা matrix `M`-কে নিজের সাথে `n` বার গুণ করলে (মানে `M^n`) কী হয় — আর সেটা **দ্রুত** কীভাবে বের করি?
সরলভাবে গুণ করলে `M^n` মানে n−1 বার matrix গুণ — n বড় হলে অসম্ভব ধীর। লক্ষ্য — সংখ্যার `a^n` যেমন binary exponentiation-এ O(log n)-এ হয়, ঠিক তেমনি `M^n`-ও O(log n) matrix গুণে।
এটা কেন দরকার? কারণ **যেকোনো linear recurrence** (যেমন Fibonacci, `a(n) = c1·a(n−1) + c2·a(n−2) + ...`) একটা matrix গুণে এক ধাপ এগোয় — তাই `M^n` মানে n ধাপ এক লাফে, recurrence-এর n-তম পদ O(log n)-এ। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু এটা একটা সর্বজনীন ছাঁচ।
### Input ও output {#6-example-input-and-output}
```text
M = [[1,1],[1,0]], বিভিন্ন n-এ M^n (Fibonacci matrix):
n -> M^n মানে (top-left = F(n+1), ইত্যাদি)
----------------------------------------------------------------
1 -> [[1,1],[1,0]] M নিজেই
2 -> [[2,1],[1,1]] F(3)=2, F(2)=1
5 -> [[8,5],[5,3]] F(6)=8, F(5)=5
0 -> [[1,0],[0,1]] identity (M^0 সবসময়)
অন্য matrix — A = [[2,0],[0,3]] (diagonal):
n -> A^n
----------------------------------------------------------------
3 -> [[8,0],[0,27]] 2³=8, 3³=27 (diagonal-এ সরাসরি ঘাত)
mod সহ — M^n mod 1000:
n = 20, M = [[1,1],[1,0]] -> top-right = F(20) mod 1000 = 6765 mod 1000 = 765
```
খেয়াল করো: **M^0 = identity** (সংখ্যার a⁰ = 1-এর মতো) — গুরুত্বপূর্ণ edge case। আর diagonal matrix-এর ঘাত মানে প্রতিটা diagonal element-এর আলাদা ঘাত — দ্রুত cross-check-এ কাজে লাগে। বড় n-এ mod নিয়ে কাজ করি যাতে সংখ্যা না ফেটে যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা state machine — প্রতিটা matrix গুণ মানে "এক ধাপ এগোও"। ধরো তুমি একটা সিঁড়িতে দাঁড়িয়ে, আর M হলো "এক ধাপ ওঠার নিয়ম"। তাহলে `M^n` মানে "n ধাপ ওঠা"।
এখন n যদি 1000 হয়, তুমি কি 999 বার একটা একটা করে ধাপ গুনবে? না! তুমি চালাক — আগে "2 ধাপ একসাথে" (M²) শেখো, তারপর "4 ধাপ" (M⁴ = M²·M²), "8 ধাপ"... । 1000 = 512 + 256 + ... এভাবে ভেঙে মাত্র গুটিকয় "বড় লাফ" জোড়া দিয়ে 1000 ধাপ পৌঁছে যাও।
এটাই matrix exponentiation — "এক ধাপের নিয়ম"-কে বারবার বর্গ করে "বিশাল লাফের নিয়ম" বানিয়ে নেওয়া, ঠিক যেমন সংখ্যার ঘাত binary-তে ভেঙে দ্রুত করা হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **029 (Binary Exponentiation)**। 029-এর গোটা কাঠামো — `n & 1` দেখে result-এ গুণ, তারপর base square, `n >>= 1` — এখানে হুবহু একই, শুধু "গুণ" এখন `mat_mult`, আর "result শুরু" এখন identity matrix (`[[1,0],[0,1]]`)।
পেছনে আরও দাঁড়িয়ে আছে divide-and-conquer-এর চিন্তা (`M^n = M^(n/2) · M^(n/2)`)। আর এর উপরে দাঁড়াবে **132 (Fibonacci via matrix)** আর **133 (fast doubling)** — দুটোই এই matrix-power-এর সরাসরি প্রয়োগ। README-র recommended order-এ তাই 131 → 132 → 133 trilogy।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **binary exponentiation, সংখ্যার বদলে matrix-এ**। 029-এ `a^n` বের করতে আমরা n-কে binary-তে ভেঙে square করতে করতে এগিয়েছিলাম:
```
a^13 = a^8 · a^4 · a^1 (13 = 1101 in binary)
```
ঠিক একই খেলা matrix-এ চলে, কারণ matrix গুণ **associative** (`(AB)C = A(BC)`)। তাই:
```
M^n = (M-কে square করতে করতে, n-এর binary bit ধরে যেগুলো লাগে গুণ)
```
দুটো জিনিস লাগে: matrix গুণের নিয়ম, আর "1" হিসেবে **identity matrix** (যার সাথে গুণ করলে কিছু বদলায় না — সংখ্যার 1-এর মতো)। এই level CP-leaning হলেও মূল সুর সরল — যা সংখ্যায় পারো, matrix-এও পারো, শুধু "গুণ" আর "1"-এর সংজ্ঞা বদলে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরলতম idea — **M-কে n বার (আসলে n−1 বার গুণ) একটা একটা করে নিজের সাথে গুণ করা**:
```python
def mat_mult(A, B):
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for k in range(n):
for j in range(n):
C[i][j] += A[i][k] * B[k][j]
return C
def mat_pow_brute(M, n):
R = [[1 if i == j else 0 for j in range(len(M))] for i in range(len(M))] # identity
for _ in range(n):
R = mat_mult(R, M)
return R
```
ছোট n-এ (যেমন 5) এটা নিখুঁত — শুধু n বার গুণ। আমাদের fast version-এর উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য পরিষ্কার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে ঠিক `n` বার, আর প্রতিবার একটা matrix গুণ (k×k matrix-এ O(k³))। তাই মোট O(n · k³)।
```text
n ছোট (5): 5 বার গুণ — তাৎক্ষণিক
n = 10⁹: 10⁹ বার গুণ — অসম্ভব (ঘণ্টার পর ঘণ্টা)
n = 10¹⁸: একদম অসম্ভব
binary expo: ~log₂(n) বার গুণ — n=10¹⁸-এও মাত্র ~60 বার!
```
বড় n-এ brute force সম্পূর্ণ অচল — Fibonacci-র 10¹⁸-তম পদ চাইলে 10¹⁸ বার গুণ অসম্ভব। অথচ binary exponentiation মাত্র ~60 matrix গুণে সেটা দেয়। এটাই O(n) → O(log n)-এর জাদু।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **matrix গুণ associative, তাই সংখ্যার binary exponentiation হুবহু matrix-এ চলে।** কাঠামো 029-এর মতোই:
```text
1. R = identity matrix (matrix জগতের "1")
2. while n > 0:
যদি n-এর শেষ bit 1 (n & 1): R = R · M
M = M · M (square)
n = n >> 1 (পরের bit-এ যাও)
3. R = M^n
```
কেন কাজ করে: n-কে binary-তে ভাঙলে `M^n = ∏ M^(2^i)` (যেসব bit 1)। প্রতি ধাপে M square হয়ে `M^1, M^2, M^4, ...` হয়, আর bit 1 হলে R-এ সেটা গুণ। ~log₂n ধাপে শেষ।
mod লাগলে প্রতিটা matrix গুণের ভেতরে `% mod` দিয়ে দিই, যাতে সংখ্যা না ফেটে যায় (CP-তে প্রায়ই mod 10⁹+7)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **সংখ্যার `a^n`-এ যা পারো, matrix-এও তাই — শুধু "গুণ" বদলে matrix গুণ, আর "1" বদলে identity matrix।**
brute force n বার একে একে গুণছিল; tweak হলো — n-কে binary-তে ভেঙে M-কে square করতে করতে এগোও, প্রয়োজন মতো R-এ গুণ। O(n) থেকে O(log n)-এ নেমে এল। আর গভীর tweak: যেকোনো linear recurrence-কে এই matrix-এ ভরে ফেলা যায় — তখন n-তম পদও O(log n)-এ (যা 132-তে দেখব)।
### ছবিতে বোঝা {#5-visual-explanation}
`M^5` binary exponentiation-এ — 5 = 101 (binary):
```text
M = [[1, 1],
[1, 0]] (Fibonacci matrix, উদাহরণ হিসেবে)
n = 5 = 101 (binary), result R শুরু = identity = [[1,0],[0,1]]
bit (ডান থেকে) | n & 1 | R আপডেট | M আপডেট (square)
---------------+-------+----------------+------------------
1 (LSB) | 1 | R = R·M = M | M = M·M = M²
0 | 0 | (R অপরিবর্তিত) | M = M²·M² = M⁴
1 | 1 | R = R·M⁴ | (লুপ শেষ)
R = M · M⁴ = M⁵ ✓ (মাত্র 3টা square + 2টা গুণ, 4 বার নয়)
matrix গুণের নিয়ম (2×2):
[a b] [e f] [a·e+b·g a·f+b·h]
[c d]·[g h] = [c·e+d·g c·f+d·h]
```
লক্ষ করো — naive হলে M^5 মানে 4 বার গুণ; binary-তে মাত্র ~log₂5 ≈ 3 square আর কয়েকটা গুণ। n যত বড় হবে, এই সাশ্রয় তত নাটকীয়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`mat_pow(M, 5)` যেখানে M = [[1,1],[1,0]] — 5 = 101 (binary):
| step | n (binary) | n & 1 | R আপডেট | M আপডেট (square) |
| --- | --- | --- | --- | --- |
| শুরু | 101 (5) | — | R = identity = [[1,0],[0,1]] | M = [[1,1],[1,0]] |
| 1 | 101 | 1 | R = R·M = [[1,1],[1,0]] | M = M² = [[2,1],[1,1]] |
| 2 | 10 (2) | 0 | R অপরিবর্তিত | M = M⁴ = [[5,3],[3,2]] |
| 3 | 1 | 1 | R = R·M⁴ = [[8,5],[5,3]] | (n = 0, লুপ শেষ) |
চূড়ান্ত R = [[8, 5], [5, 3]] = M⁵। যাচাই: এটাই Fibonacci matrix M⁵, যার top-right 5 = F(5), top-left 8 = F(6) ✓। মাত্র 3 step-এ M⁵ পেলাম, 4 বার গুণ না করে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mat_mult(A, B, mod=None):
"""দুটো square matrix গুণ। mod দিলে প্রতিটা ঘরে % mod।"""
n, m, p = len(A), len(B[0]), len(B)
C = [[0] * m for _ in range(n)]
for i in range(n):
Ai = A[i]
for k in range(p):
a = Ai[k]
if a == 0:
continue
Bk = B[k]
for j in range(m):
C[i][j] += a * Bk[j]
if mod is not None:
C[i][j] %= mod
return C
def identity(n):
"""n×n identity matrix (matrix জগতের '1')।"""
return [[1 if i == j else 0 for j in range(n)] for i in range(n)]
def mat_pow(M, power, mod=None):
"""M^power — binary exponentiation, O(k³ · log power)।"""
n = len(M)
R = identity(n)
M = [row[:] for row in M] # M-এর কপি (input অক্ষত রাখি)
while power > 0:
if power & 1:
R = mat_mult(R, M, mod)
M = mat_mult(M, M, mod)
power >>= 1
return R
# --- ছোট test গুলো (সব pass করা উচিত) ---
def mat_pow_brute(M, n, mod=None):
R = identity(len(M))
for _ in range(n):
R = mat_mult(R, M, mod)
return R
FIB = [[1, 1], [1, 0]]
# fast বনাম brute — n = 0..30 সব মেলাও
for n in range(0, 31):
assert mat_pow(FIB, n) == mat_pow_brute(FIB, n), f"M^{n} অমিল"
# M^0 = identity
assert mat_pow(FIB, 0) == [[1, 0], [0, 1]]
# M^1 = M
assert mat_pow(FIB, 1) == FIB
# diagonal matrix-এর ঘাত diagonal-এ সরাসরি
assert mat_pow([[2, 0], [0, 3]], 3) == [[8, 0], [0, 27]]
# Fibonacci-র সাথে মিল: M^n-এর top-right = F(n)
def fib_naive(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
for n in range(0, 25):
assert mat_pow(FIB, n)[0][1] == fib_naive(n), f"F({n}) অমিল"
# mod সহ: F(20) mod 1000 = 6765 mod 1000 = 765
assert mat_pow(FIB, 20, 1000)[0][1] == 765
# 3×3 matrix-ও কাজ করে
A = [[1, 1, 0], [0, 1, 1], [0, 0, 1]]
assert mat_pow(A, 2) == [[1, 2, 1], [0, 1, 2], [0, 0, 1]]
print(mat_pow(FIB, 5)) # [[8, 5], [5, 3]]
print(mat_pow(FIB, 10)[0][1]) # 55 (F(10))
print(mat_pow([[2, 0], [0, 3]], 3)) # [[8, 0], [0, 27]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def mat_mult(A, B, mod=None):
...
for i in range(n):
for k in range(p):
a = Ai[k]
...
for j in range(m):
C[i][j] += a * Bk[j]
```
স্ট্যান্ডার্ড matrix গুণ — C[i][j] = ∑ A[i][k]·B[k][j]। i-k-j order-এ লিখলে cache-friendly আর `a == 0` হলে skip করে একটু দ্রুত। mod দিলে প্রতিটা যোগের পর `% mod`।
```
def identity(n):
return [[1 if i == j else 0 ...]]
```
identity matrix — diagonal-এ 1, বাকি 0। এটাই matrix জগতের "1", যেকোনো M-এর সাথে গুণ করলে M অপরিবর্তিত।
```
def mat_pow(M, power, mod=None):
R = identity(n)
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
```
029-এর binary exponentiation-এর হুবহু matrix রূপ — R identity থেকে শুরু; power-এর শেষ bit 1 হলে R-এ M গুণ; প্রতি ধাপে M square; `power >>= 1` দিয়ে পরের bit। M-এর কপি নিচ্ছি যাতে input matrix নষ্ট না হয়।
বাকি test অংশে fast বনাম brute (n = 0..30), M^0 = identity, Fibonacci-র সাথে মিল, mod, আর 3×3 matrix সব যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
[[8, 5], [5, 3]]
55
[[8, 0], [0, 27]]
সব test pass!
```
`mat_pow(FIB, 5)` → [[8,5],[5,3]] (Fibonacci matrix M⁵, section 11-এর dry run-এর সাথে মিল)। `mat_pow(FIB, 10)[0][1]` → 55 (top-right = F(10) = 55)। `mat_pow([[2,0],[0,3]], 3)` → [[8,0],[0,27]] (diagonal-এ 2³, 3³)। তার আগে সব assert (fast vs brute, Fibonacci, mod, 3×3) pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(k³ · log n)** — যেখানে k হলো matrix-এর মাত্রা (k×k), n হলো ঘাত। binary exponentiation ~log₂n বার matrix গুণ করে, আর প্রতিটা গুণ O(k³)। Fibonacci-তে k = 2 (ছোট ধ্রুবক), তাই কার্যত O(log n)। brute force-এর O(n · k³)-এর তুলনায় বিশাল লাফ — n = 10¹⁸-এও মাত্র ~60 গুণ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(k²)** — কয়েকটা k×k matrix (R, M, temporary C) রাখা লাগে। recursion নেই (iterative), তাই extra stack নেই। Fibonacci-তে k = 2, তাই কার্যত O(1)। ঘাত n বড় হলেও memory বাড়ে না — শুধু matrix-এর আকারের উপর নির্ভর।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **matrix গুণের order উল্টে ফেলা** — matrix গুণ commutative **নয়** (`A·B ≠ B·A` সাধারণত)। recurrence-এর matrix বসানোর সময় order ঠিক রাখো, নাহলে ভুল উত্তর।
2. **identity matrix ভুল বা বাদ দেওয়া** — R-কে identity দিয়ে শুরু করতে হবে (diagonal 1)। 0-matrix বা ভুল শুরু দিলে সব গুণ 0।
3. **M^0 না সামলানো** — power = 0 হলে identity ফেরত (লুপ চলে না) — এটাই সঠিক; আলাদা করে ভুল কিছু না করলেই হলো।
4. **mod ভেতরে না দেওয়া (বড় সংখ্যায়)** — C++/Java-তে matrix গুণে সংখ্যা overflow করে; প্রতিটা গুণ-যোগে `% mod` দিতে হবে। Python-এ overflow নেই কিন্তু সংখ্যা বিশাল হয়ে ধীর হতে পারে।
5. **input matrix নষ্ট করা** — mat_pow-এ M square করার সময় মূল input বদলে গেলে caller-এ সমস্যা; কপি নিয়ে কাজ করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Throwing Dice / Graph Paths** (