福
福

雨辰枫司的小栈

快速幂

  • 822 字
  • 条评论
  1. 1. 模板
  2. 2. 矩阵模板

就是利用了二进制原理来进行运算

模板

1
2
3
4
5
6
7
8
def pows(a,n,mod):
    ans = 1
    while n > 0:
        if (n & 1) == 1:
            ans *= a % mod
        a *= a % mod
        n >>= 1
    return ans % mod

矩阵模板

可以用于多次线性变换

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

, ,