147 — Matrix Power on Graphs¶
Level 10-এর matrix exponentiation (problem 131) ফিরে এলো — এবার graph-এর পোশাকে। মূল চমক: একটা graph-এর adjacency matrix-এর
k-তম power বলে দেয় "ঠিকkধাপে এক vertex থেকে আরেক vertex-এ কয় উপায়ে যাওয়া যায়"। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।
Source¶
- Original source: Classic CP technique — counting length-k walks via adjacency matrix power
- Platform: Classic CP technique (related: CP-Algorithms binary exponentiation)
- Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- Difficulty: Hard
- Pattern: path counting (A^k = length-k walk count)
- Basic idea inherited from: 131 (matrix exponentiation)
1. Problem in simple words¶
একটা directed graph দেওয়া (কোন vertex থেকে কোন vertex-এ যাওয়া যায়)। জিজ্ঞেস: vertex i থেকে vertex j-তে ঠিক k ধাপে (ঠিক kটা edge পেরিয়ে) কয় উপায়ে যাওয়া যায়?
উদাহরণ: একটা triangle graph (3 vertex, প্রত্যেকে বাকি দুটোর সাথে যুক্ত)। vertex 0 থেকে আবার vertex 0-তে ঠিক 2 ধাপে কয় উপায়? উত্তর 2 — পথ 0→1→0 আর 0→2→0।
মূল কৌশল: graph-কে একটা adjacency matrix A-তে লেখো (A[i][j] = 1 যদি i→j edge থাকে), তারপর A-এর k-তম power বের করো — Aᵏ[i][j] ই হলো উত্তর। আর k বিশাল (10¹⁸) হলেও matrix exponentiation দিয়ে দ্রুত।
এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; graph (
../../05-graphs/) আর matrix expo (131) ঝালিয়ে ফিরলে এটা সহজ লাগবে।
2. What is the math idea?¶
মূল ধারণা — matrix গুণের সংজ্ঞাই walk গোনে:
A²[i][j] = Σ_m A[i][m] · A[m][j]
= "এমন কতগুলো মধ্যবর্তী vertex m আছে যাতে i → m আর m → j দুটোই edge"
= i থেকে j-তে ঠিক 2 ধাপে walk-এর সংখ্যা
Induction-এ এগোলে: Aᵏ[i][j] = i থেকে j-তে ঠিক k ধাপে walk-সংখ্যা। কারণ Aᵏ = Aᵏ⁻¹ · A — k−1 ধাপের walk-এর সাথে আরেকটা edge জোড়া। আর বড় k-এর জন্য binary exponentiation (131): Aᵏ-কে A-এর বর্গ-করে-করে O(V³ log k)-এ পাওয়া যায়।
3. Which basic idea does this inherit from?¶
সরাসরি matrix exponentiation (problem 131) থেকে। 131-এ শিখেছিলে কীভাবে একটা matrix-এর k-তম power দ্রুত (binary exponentiation দিয়ে, O(d³ log k)) বের করতে হয় — Fibonacci-র মতো linear recurrence দ্রুত করতে। এখানে সেই একই যন্ত্র, কিন্তু matrix-টা এবার graph-এর adjacency matrix, আর power-এর অর্থ হলো walk count।
নতুন idea: graph-এর সাথে matrix-এর এই সেতু — "edge আছে কিনা" (A)-এর power "কয় ধাপে কয় উপায়ে" বলে দেয়। তাই এটা 131-এর কৌশল + graph-চিন্তার মিলন; concept-notes-ও বলছে "131 ফিরে এলো"।
4. Real-life analogy¶
ভাবো কয়েকটা শহরের মধ্যে সরাসরি ফ্লাইট-রুট আছে (graph-এর edge)। তুমি জানতে চাও — শহর A থেকে শহর B-তে ঠিক k টা ফ্লাইট নিয়ে (মাঝে যেকোনো শহরে নামা চলে, এমনকি একই শহরে দুবার) কত আলাদা ভ্রমণ-পরিকল্পনা সম্ভব।
এক-ফ্লাইটের রুট-টেবিল (A) তোমার হাতে। দুই-ফ্লাইটের সব পরিকল্পনা পেতে তুমি ভাবো — A থেকে যে কোনো মধ্যবর্তী শহর, সেখান থেকে B। এটাই matrix গুণ। তিন-ফ্লাইট, চার-ফ্লাইট... প্রতিবার আরেকটা ফ্লাইট জোড়া = আরেকবার A দিয়ে গুণ। k বিশাল হলে চালাকি — A², A⁴, A⁸... বর্গ করে করে দ্রুত পৌঁছানো।
5. Visual explanation¶
Triangle graph-এ A² কীভাবে walk গোনে:
triangle graph (0,1,2 — প্রত্যেকে বাকি দুটোর সাথে):
0
/ \
1---2
A = [0 1 1] A[i][j]=1 মানে i->j edge
[1 0 1]
[1 1 0]
A² = A · A:
A²[0][0] = A[0][0]·A[0][0] + A[0][1]·A[1][0] + A[0][2]·A[2][0]
= 0·0 + 1·1 + 1·1 = 2
= পথ 0→1→0 আর 0→2→0 (ঠিক 2টা length-2 walk)
A² = [2 1 1]
[1 2 1]
[1 1 2]
কর্ণে 2 (নিজে ফিরে আসার 2 পথ), বাকিতে 1।
লক্ষ করো — এগুলো walk (vertex পুনরাবৃত্তি চলে), simple path নয়।
6. Example input and output¶
graph k প্রশ্ন উত্তর
-------------------------------------------------------------
triangle (3-cycle) 2 0→0 walk 2 (0→1→0, 0→2→0)
triangle 2 0→1 walk 1 (0→2→1)
path 0-1-2 (line) 2 0→2 walk 1 (0→1→2)
path 0-1-2 1 0→2 walk 0 (সরাসরি edge নেই)
single edge 0→1 1 0→1 walk 1
A^0 = identity -> 0 ধাপে i→i: 1 উপায় (থেমে থাকা), i→j: 0
মূল edge case: k = 0 হলে A⁰ = identity — একই vertex-এ থাকার 1 উপায় (কোনো ধাপ না নেওয়া), ভিন্ন vertex-এ 0; আর বড় count modular রাখতে হয় (10⁹+7)।
7. Brute force thinking¶
Matrix power না ভেবে — সরাসরি recursion/DP: "s থেকে step ধাপে e-তে কয় উপায়?" প্রতিটা ধাপে সব প্রতিবেশীতে ছড়াই:
def count_walks_brute(adj, k, s, e):
n = len(adj)
def rec(node, steps):
if steps == k:
return 1 if node == e else 0
total = 0
for nxt in range(n):
if adj[node][nxt]:
total += rec(nxt, steps + 1) # আরেকটা edge পেরোও
return total
return rec(s, 0)
এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয়। আর matrix power যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু k বড় হলে এই গাছ ভয়ংকর ছড়ায় (memoization করলেও k-এর সাথে linear, যা বিশাল k-তে অসম্ভব)।
8. Why brute force may be slow¶
Recursion গাছের গভীরতা k, প্রতি node-এ V শাখা — O(V^k) (memo ছাড়া)। DP/memo দিয়ে O(k · V²)-এ নামে, কিন্তু k যদি বিশাল হয়:
k = 1000 -> DP O(k·V²) ঠিক আছে
k = 10^18 -> k বার loop করাই অসম্ভব (memo সত্ত্বেও)
matrix power: O(V³ · log k) -> k = 10^18 হলেও log k ≈ 60 ধাপ
মূল সমস্যা — k নিজেই এত বড় যে k ধাপে কিছু করাও যায় না। matrix exponentiation log k-এ নামিয়ে দেয় (131-এর সেই জাদু)।
9. Better thinking¶
মূল insight: Aᵏ[i][j] = length-k walk count, আর Aᵏ দ্রুত পাওয়া যায় binary exponentiation দিয়ে।
Aᵏ বের করা: k-কে binary-তে ভাঙো
A^13 = A^8 · A^4 · A^1 (13 = 1101)
A, A², A⁴, A⁸ ... বর্গ করে করে বানাও, দরকারিগুলো গুণ করো
-> log k টা matrix গুণ, প্রতিটা O(V³)
তাই পুরো কাজ O(V³ log k)। বিশাল k-তেও (10¹⁸) মাত্র ~60টা matrix গুণ — brute force-এর k ধাপের তুলনায় আকাশ-পাতাল।
10. Thinking tweak¶
এক লাইনের "আহা": "ঠিক k ধাপে কয় উপায়ে" প্রশ্ন দেখলেই adjacency matrix-এর k-তম power ভাবো — matrix গুণের সংজ্ঞাই মধ্যবর্তী vertex-গুলোর উপর যোগফল, মানে walk গোনা।
সবচেয়ে বড় ফাঁদ: walk আর simple path গুলিয়ে ফেলা (concept-notes mistake #8)। Aᵏ গোনে walk — যেখানে vertex/edge বারবার আসতে পারে (0→1→0 বৈধ)। কিন্তু "কোনো vertex দুবার নয়" (simple path) চাইলে এ পথ নয়; সেটা সম্পূর্ণ ভিন্ন (NP-hard ঘরানা)। আর বড় count-এ mod 10⁹+7 নিতে ভুলো না।
11. Step-by-step dry run¶
Triangle graph, 0→0 ঠিক 2 ধাপে — A² বের করে:
A:[[0,1,1],[1,0,1],[1,1,0]]।A² = A · A— cell(0,0)হিসাব:Σ_m A[0][m]·A[m][0]=0·0 + 1·1 + 1·1= 2।- cell
(0,1):A[0][0]·A[0][1] + A[0][1]·A[1][1] + A[0][2]·A[2][1]=0·1 + 1·0 + 1·1= 1। - পুরো
A² = [[2,1,1],[1,2,1],[1,1,2]]। - উত্তর:
A²[0][0] = 2— মানে0→0ঠিক 2 ধাপে 2 উপায় (0→1→0,0→2→0)। brute force-ও 2 বলে ✓।
12. Python solution¶
def mat_mult(A, B, mod=10 ** 9 + 7):
"""দুই matrix গুণ (mod সহ)।"""
n, p, m = len(A), len(B), len(B[0])
C = [[0] * m for _ in range(n)]
for i in range(n):
for t in range(p):
if A[i][t]: # 0 হলে skip (সামান্য দ্রুত)
a = A[i][t]
for j in range(m):
C[i][j] = (C[i][j] + a * B[t][j]) % mod
return C
def mat_pow(A, k, mod=10 ** 9 + 7):
"""A-এর k-তম power, binary exponentiation-এ (131-এর কৌশল)।"""
n = len(A)
result = [[int(i == j) for j in range(n)] for i in range(n)] # identity
while k:
if k & 1:
result = mat_mult(result, A, mod)
A = mat_mult(A, A, mod) # বর্গ করো
k >>= 1
return result
def count_walks(adj, k, s, e, mod=10 ** 9 + 7):
"""s থেকে e-তে ঠিক k ধাপে walk-সংখ্যা = (A^k)[s][e]।"""
return mat_pow(adj, k, mod)[s][e]
def count_walks_brute(adj, k, s, e):
"""সরল recursion — যাচাইয়ের জন্য।"""
n = len(adj)
def rec(node, steps):
if steps == k:
return 1 if node == e else 0
return sum(rec(nxt, steps + 1) for nxt in range(n) if adj[node][nxt])
return rec(s, 0)
# --- ছোট test গুলো (সব pass করা উচিত) ---
triangle = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
A2 = mat_pow(triangle, 2)
assert A2 == [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
assert count_walks(triangle, 2, 0, 0) == 2 # 0→1→0, 0→2→0
assert count_walks(triangle, 2, 0, 1) == 1 # 0→2→1
line = [[0, 1, 0], [1, 0, 1], [0, 1, 0]] # path 0-1-2
assert count_walks(line, 2, 0, 2) == 1 # 0→1→2
assert count_walks(line, 1, 0, 2) == 0 # সরাসরি edge নেই
# A^0 = identity
A0 = mat_pow(triangle, 0)
assert A0 == [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
# brute force-এর সাথে এলোমেলো ছোট graph-এ মিল (সঠিকতার প্রমাণ)
import random
for _ in range(60):
n = random.randint(2, 4)
adj = [[random.randint(0, 1) for _ in range(n)] for _ in range(n)]
k = random.randint(1, 4)
Ak = mat_pow(adj, k)
for s in range(n):
for e in range(n):
assert Ak[s][e] == count_walks_brute(adj, k, s, e), (adj, k, s, e)
print(count_walks(triangle, 2, 0, 0)) # 2
print(count_walks(triangle, 3, 0, 0)) # 2
print(count_walks(line, 2, 0, 2)) # 1
print("সব test pass!")
13. Line-by-line explanation¶
Matrix গুণের সংজ্ঞা: C[i][j] = Σ_t A[i][t]·B[t][j]। এই যোগফলই "মধ্যবর্তী vertex t-এর উপর সব পথ" — walk গোনার কেন্দ্র। A[i][t] 0 হলে skip (সামান্য দ্রুত), আর প্রতি ধাপে % mod overflow ঠেকায়।
result = [[int(i == j) for j in range(n)] for i in range(n)]
while k:
if k & 1:
result = mat_mult(result, A, mod)
A = mat_mult(A, A, mod)
k >>= 1
131-এর binary exponentiation — শুরু identity (A⁰), k-এর প্রতিটা bit দেখি: bit 1 হলে বর্তমান A-power গুণ করি, তারপর A বর্গ করি, bit সরাই। log k ধাপে Aᵏ।
পুরো উত্তর — Aᵏ বের করে [s][e] cell পড়া।
বাকি count_walks_brute সরল recursion (যাচাইয়ের জন্য), আর assert গুলো মিলিয়ে দেখে: A²-এর মান, নির্দিষ্ট walk, A⁰ identity, আর 60টা random graph-এ brute force-এর সাথে মিল। সব মিললে সব test pass!।
14. Output walkthrough¶
চালালে ছাপবে:
প্রথম লাইন triangle-এ 0→0 2 ধাপে → 2। দ্বিতীয় 0→0 3 ধাপে → 2 (0→1→2→0, 0→2→1→0)। তৃতীয় line graph-এ 0→2 2 ধাপে → 1। তার আগের সব assert চুপচাপ pass — matrix power আর brute force সব ছোট graph-এ একমত। সবশেষে সব test pass!।
15. Time complexity¶
O(V³ · log k) — Aᵏ বের করতে log kটা matrix গুণ, প্রতিটা O(V³) (V = vertex সংখ্যা)। brute force ছিল O(V^k) বা memo-তে O(k·V²) — বিশাল k-তে অসম্ভব। matrix power-এ k = 10¹⁸ হলেও log k ≈ 60 ধাপ।
16. Space complexity¶
O(V²) — কয়েকটা V×V matrix (result, current power, temp)। graph-এর আকারের বর্গ; k-এর সাথে বাড়ে না (binary exponentiation in-place-ঘেঁষা)।
17. Common mistakes¶
- Walk আর simple path গুলিয়ে ফেলা —
Aᵏগোনে walk (vertex পুনরাবৃত্তি চলে); simple path চাইলে এ পথ নয় (concept-notes mistake #8)। - mod ভুলে যাওয়া — walk count দ্রুত বিশাল হয়; প্রতি গুণ-যোগে
% (10⁹+7)না নিলে overflow/ভুল। A⁰-কে শূন্য matrix ভাবা —A⁰ = identity(0 ধাপে নিজের জায়গায় 1 উপায়); শূন্য নয়।- Matrix গুণ non-commutative ভুলে —
result·AআরA·resultআলাদা; binary exponentiation-এ ক্রম ঠিক রাখো (যদিও power-এ একই matrix বলে এখানে সমস্যা কম)। - Directed/undirected গুলিয়ে ফেলা — undirected হলে
Asymmetric (A[i][j]=A[j][i]); directed হলে নয় — adjacency সঠিক দিকে বসাও।
18. Harder problems that inherit this idea¶
- CSES — Graph Paths I / II (https://cses.fi/problemset/) — ঠিক
k-edge path count / min-cost, matrix power (min-plus সহ)। - CP-Algorithms — Binary Exponentiation (https://cp-algorithms.com/algebra/binary-exp.html) — matrix power-এর ভিত্তি।
- LeetCode — Knight Dialer (https://leetcode.com/problems/knight-dialer/) —
k-step path count on a fixed graph; matrix power-এ optimize করা যায়।
19. Pattern learned¶
Matrix power on graphs (path counting) — adjacency matrix A-এর Aᵏ[i][j] = i→j length-k walk count; কারণ matrix গুণ = মধ্যবর্তী vertex-এর উপর যোগ। binary exponentiation-এ O(V³ log k), বিশাল k-তেও। (walk, simple path নয়।)
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "'ঠিক k ধাপে কয় উপায়ে' = adjacency matrix-এর Aᵏ; matrix গুণের সংজ্ঞাই walk গোনে। binary exponentiation-এ O(V³ log k), k=10¹⁸ হলেও। সাবধান — এটা walk (vertex repeat চলে), simple path নয়; mod নাও।"
পরের ধাপ → 148 — Inclusion-Exclusion Hard (counting জোড়ার প্রথম — forbidden property)। শিকড় → 131 — Matrix Exponentiation, graph → ../../05-graphs/।
ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।