Problem link ও উৎস
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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) ঝালিয়ে ফিরলে এটা সহজ লাগবে।
### বাইরের অনুশীলনের সঙ্গে সম্পর্ক {#_1}
[CSES Graph Paths I](https://cses.fi/problemset/task/1723/)-এ নির্দিষ্ট দুই vertex-এর মধ্যে ঠিক kটি edge ব্যবহার করে walk-এর সংখ্যা modulo 10⁹+7 চায়। একই vertex/edge আবার ব্যবহার করা যায়; এটি simple path গোনা নয়। এই নোটের adjacency-matrix পদ্ধতির সরাসরি অনুশীলন।
### Input ও output {#6-example-input-and-output}
```text
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)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো কয়েকটা শহরের মধ্যে সরাসরি ফ্লাইট-রুট আছে (graph-এর edge)। তুমি জানতে চাও — শহর A থেকে শহর B-তে **ঠিক `k` টা ফ্লাইট** নিয়ে (মাঝে যেকোনো শহরে নামা চলে, এমনকি একই শহরে দুবার) কত আলাদা ভ্রমণ-পরিকল্পনা সম্ভব।
এক-ফ্লাইটের রুট-টেবিল (`A`) তোমার হাতে। দুই-ফ্লাইটের সব পরিকল্পনা পেতে তুমি ভাবো — A থেকে যে কোনো মধ্যবর্তী শহর, সেখান থেকে B। এটাই matrix গুণ। তিন-ফ্লাইট, চার-ফ্লাইট... প্রতিবার আরেকটা ফ্লাইট জোড়া = আরেকবার `A` দিয়ে গুণ। `k` বিশাল হলে চালাকি — `A²`, `A⁴`, `A⁸`... বর্গ করে করে দ্রুত পৌঁছানো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 ফিরে এলো"।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা — **matrix গুণের সংজ্ঞাই walk গোনে**:
```text
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)`-এ পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
Matrix power না ভেবে — সরাসরি recursion/DP: "`s` থেকে `step` ধাপে `e`-তে কয় উপায়?" প্রতিটা ধাপে সব প্রতিবেশীতে ছড়াই:
```python
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` যদি বিশাল হয়:
```text
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** দিয়ে।
```text
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 নিতে ভুলো না।
### ছবিতে বোঝা {#5-visual-explanation}
Triangle graph-এ `A²` কীভাবে walk গোনে:
```text
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 নয়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
Triangle graph, `0→0` ঠিক 2 ধাপে — `A²` বের করে:
1. **`A`:** `[[0,1,1],[1,0,1],[1,1,0]]`।
2. **`A² = A · A`** — cell `(0,0)` হিসাব: `Σ_m A[0][m]·A[m][0]` = `0·0 + 1·1 + 1·1` = 2।
3. 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।
4. পুরো `A² = [[2,1,1],[1,2,1],[1,1,2]]`।
5. **উত্তর:** `A²[0][0] = 2` — মানে `0→0` ঠিক 2 ধাপে 2 উপায় (`0→1→0`, `0→2→0`)। brute force-ও 2 বলে ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
if A[i][t]:
a = A[i][t]
for j in range(m):
C[i][j] = (C[i][j] + a * B[t][j]) % mod
```
Matrix গুণের সংজ্ঞা: `C[i][j] = Σ_t A[i][t]·B[t][j]`। এই যোগফলই "মধ্যবর্তী vertex `t`-এর উপর সব পথ" — walk গোনার কেন্দ্র। `A[i][t]` 0 হলে skip (সামান্য দ্রুত), আর প্রতি ধাপে `% mod` overflow ঠেকায়।
```text
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ᵏ`।
```text
def count_walks(adj, k, s, e, mod=10 ** 9 + 7):
return mat_pow(adj, k, mod)[s][e]
```
পুরো উত্তর — `Aᵏ` বের করে `[s][e]` cell পড়া।
বাকি `count_walks_brute` সরল recursion (যাচাইয়ের জন্য), আর `assert` গুলো মিলিয়ে দেখে: `A²`-এর মান, নির্দিষ্ট walk, `A⁰` identity, আর 60টা random graph-এ brute force-এর সাথে মিল। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
2
2
1
সব test pass!
```
প্রথম লাইন 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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **Walk আর simple path গুলিয়ে ফেলা** — `Aᵏ` গোনে walk (vertex পুনরাবৃত্তি চলে); simple path চাইলে এ পথ নয় (concept-notes mistake #8)।
2. **mod ভুলে যাওয়া** — walk count দ্রুত বিশাল হয়; প্রতি গুণ-যোগে `% (10⁹+7)` না নিলে overflow/ভুল।
3. **`A⁰`-কে শূন্য matrix ভাবা** — `A⁰ = identity` (0 ধাপে নিজের জায়গায় 1 উপায়); শূন্য নয়।
4. **Matrix গুণ non-commutative ভুলে** — `result·A` আর `A·result` আলাদা; binary exponentiation-এ ক্রম ঠিক রাখো (যদিও power-এ একই matrix বলে এখানে সমস্যা কম)।
5. **Directed/undirected গুলিয়ে ফেলা** — undirected হলে `A` symmetric (`A[i][j]=A[j][i]`); directed হলে নয় — adjacency সঠিক দিকে বসাও।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Graph Paths I / II** (