1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def matrixMul(A,B):
if len(A[0]) != len(B):
return None
ter = len(B)
ans = [[0] * len(B[0]) for i in range(len(A))]
for i in range(len(ans)):
for j in range(len(ans[0])):
for k in range(ter):
ans[i][j] += (A[i][k] * B[k][j])
return ans
def getE(n):
ret = [[0] * n for i in range(n)]
for i in range(n):
ret[i][i] = 1
return ret
def pows(A,n):
ans = getE(len(A))
while n > 0:
if (n & 1) == 1:
ans = matrixMul(ans,A)
A = matrixMul(A,A)
n >>= 1
return ans
|