131 — Matrix Exponentiation¶
এই note-এ আমরা একটা দারুণ কৌশল শিখব — recurrence-কে matrix-এ বদলে binary exponentiation চালানো, যাতে n-তম পদ O(log n)-এ পাওয়া যায়। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — তবে matrix exponentiation CP-তে অসম্ভব দরকারি (Codeforces, USACO Guide-এ classic)। আর divide-and-conquer on exponent-এর চিন্তাটা interview-তেও মাঝে মাঝে কাজে লাগে। 029 (binary exponentiation) ঝালাই থাকলে এটা সহজ লাগবে।
Source¶
- Original source: Classic CP technique (USACO Guide)
- Platform: USACO Guide — https://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)
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; কিন্তু এটা একটা সর্বজনীন ছাঁচ।
2. What is the math idea?¶
মূল idea — binary exponentiation, সংখ্যার বদলে matrix-এ। 029-এ a^n বের করতে আমরা n-কে binary-তে ভেঙে square করতে করতে এগিয়েছিলাম:
ঠিক একই খেলা matrix-এ চলে, কারণ matrix গুণ associative ((AB)C = A(BC))। তাই:
দুটো জিনিস লাগে: matrix গুণের নিয়ম, আর "1" হিসেবে identity matrix (যার সাথে গুণ করলে কিছু বদলায় না — সংখ্যার 1-এর মতো)। এই level CP-leaning হলেও মূল সুর সরল — যা সংখ্যায় পারো, matrix-এও পারো, শুধু "গুণ" আর "1"-এর সংজ্ঞা বদলে।
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।
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-তে ভেঙে দ্রুত করা হয়।
5. Visual explanation¶
M^5 binary exponentiation-এ — 5 = 101 (binary):
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 যত বড় হবে, এই সাশ্রয় তত নাটকীয়।
6. Example input and output¶
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 নিয়ে কাজ করি যাতে সংখ্যা না ফেটে যায়।
7. Brute force thinking¶
সরলতম idea — M-কে n বার (আসলে n−1 বার গুণ) একটা একটা করে নিজের সাথে গুণ করা:
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³)।
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-এর মতোই:
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-তে দেখব)।
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 বার গুণ না করে।
12. Python solution¶
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।
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!।
14. Output walkthrough¶
চালালে যা ছাপবে:
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!।
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¶
- matrix গুণের order উল্টে ফেলা — matrix গুণ commutative নয় (
A·B ≠ B·Aসাধারণত)। recurrence-এর matrix বসানোর সময় order ঠিক রাখো, নাহলে ভুল উত্তর। - identity matrix ভুল বা বাদ দেওয়া — R-কে identity দিয়ে শুরু করতে হবে (diagonal 1)। 0-matrix বা ভুল শুরু দিলে সব গুণ 0।
- M^0 না সামলানো — power = 0 হলে identity ফেরত (লুপ চলে না) — এটাই সঠিক; আলাদা করে ভুল কিছু না করলেই হলো।
- mod ভেতরে না দেওয়া (বড় সংখ্যায়) — C++/Java-তে matrix গুণে সংখ্যা overflow করে; প্রতিটা গুণ-যোগে
% modদিতে হবে। Python-এ overflow নেই কিন্তু সংখ্যা বিশাল হয়ে ধীর হতে পারে। - input matrix নষ্ট করা — mat_pow-এ M square করার সময় মূল input বদলে গেলে caller-এ সমস্যা; কপি নিয়ে কাজ করো।
18. Harder problems that inherit this idea¶
- CSES — Throwing Dice / Graph Paths (https://cses.fi/problemset/task/1722) — recurrence বা graph-path গোনাকে matrix power-এ নামানো।
- Codeforces — linear recurrence / DP optimization via matrix (https://codeforces.com/problemset) — বড় n-এ DP-কে matrix exponentiation-এ ত্বরান্বিত করা।
- 132 (Fibonacci via Matrix) আর 133 (Fast Doubling) — এই repo-রই পরের দুই ধাপ; 132 এই matrix-power-এর সরাসরি প্রয়োগ, আর Level 11-এর graph-path power (147) এর উপর দাঁড়াবে।
19. Pattern learned¶
Recurrence as matrix + binary exponentiation — linear recurrence-কে square matrix-এ লিখে M^n binary exponentiation-এ O(k³ log n)-এ বের করা; "গুণ" = matrix গুণ, "1" = identity। বড় শিক্ষা: divide-and-conquer on exponent শুধু সংখ্যায় নয় — যেকোনো associative গুণে (matrix সহ) চলে; তাই n ধাপের recurrence এক লাফে log n-এ।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "matrix expo = binary exponentiation-এর matrix রূপ; R = identity, n-এর bit ধরে R·=M, M·=M; O(k³ log n)। যেকোনো linear recurrence matrix-এ ভরে n-তম পদ O(log n)-এ।" Signal: "linear recurrence-এর বিশাল n-তম পদ" বা "DP-কে matrix-এ ত্বরান্বিত" — দেখলেই এই pattern মনে পড়বে।
পরের ধাপ → 132 — Fibonacci using Matrix Exponentiation (এই matrix-power-এর সবচেয়ে বিখ্যাত প্রয়োগ)। ভিত্তি → 029 (Binary 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।