here is code…
mod = 10**9 + 7
N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
def dot(X, Y):
x = len(X)
y = len(Y[0])
z = len(Y)
C = [[0] * y for _ in range(x)]
for i in range(x):
for j in range(y):
for k in range(z):
C[i][j] += X[i][k] * Y[k][j]
C[i][j] %= mod
return C
B = [[0] * N for _ in range(N)]
for k in range(N):
B[k][k] = 1
while K > 0:
if K & 1:
B = dot(B, A)
A = dot(A, A)
K >>= 1
ans = 0
for i in range(N):
for j in range(N):
ans += B[i][j]
ans %= mod
print(ans)
The above code is working.How matrix exponenetian could give the ans.Please help me how to prove the logic is correct.
Matrix exponentiation is just a side effect.
Say, I know the number of ways to get from i to j for all i and j in length a and b. How will we find it for a+b?
let dp1[i][j] denote the number of ways to get from i to j in a steps and dp2[i][j] denote the number of ways to get from i to j in b steps. I must be somewhere after a steps. Let’s call that k. Now the number of ways to get from i to k in a steps is dp1[i][k] and the number of ways to get from k to j is dp2[k][j]. So the number of ways to go from i to j in a+b steps when I go to k after a steps is
dp1[i][k] \times dp2[k][j].
Therefore the number of ways to go to i from j after a+b steps is
\sum dp1[i][k] \times dp2[k][j] for all k.
Using this relation we can find the number of ways to go from i to j in x steps in O(log \ x) time.
11 Likes
Can anyone please enhance this explanation a bit further? Specifically wrt how it ties up ends with matrix exponentiation, wherein we need to compute A^k, where A is the given adjacency matrix.
Sure, so when you multiply two square matrices M_1 and M_2, the element at position (i, j) of the resulting matrix is defined as the dot product of the row vector M_{1i} and the column vector M_{2j}. What this dot product does exactly is it adds up M_{1ik}M_{2kj} for all 1\le k\le n. Notice that this is exactly what Everule described above. Hope this helps!