Solving Dynamic Programming with Matrix Exponentiation

ตัวอย่างโจทย์

Unweighted Undirected graph   หา จำนวน path ที่ length = k

ให้ egde มา ทุก edge = 1

A[i][j] = 1

Example
  A^2 [i][j] = 10
   คือ ในกราฟ A มี path จาก i ไป j ที่ length = 2  เท่ากับ 10 path

A^k [i][j] = number of path that length equals 'k'

https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation