【python数据结构】快速幂&矩阵快速幂&应用

100 阅读 0 评论 66 点赞

我是靠谱客的博主现代耳机，这篇文章主要介绍【python数据结构】快速幂&矩阵快速幂&应用，现在分享给大家，希望可以做个参考。

1、快速幂

复制代码

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
27
28
29
30
# 递归法
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)
#迭代法
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            ans = 1.0
            # 贡献的初始值为 x
            x_contribute = x
            # 在对 N 进行二进制拆分的同时计算答案
            while N > 0:
                if N % 2 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x_contribute
                # 将贡献不断地平方
                x_contribute *= x_contribute
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N //= 2
            return ans
        
        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

2、矩阵快速幂

复制代码

1
2
3
4
5
6
7
8
9
10
11
import numpy as np

def mat_pow(A, n):
    m = A.shape[0]
    B = np.eye(m, dtype=np.int64)
    while n > 0:
        if (n&1)!=0:
            B = np.mod(np.matmul(B, A), self.p).astype(np.int64)
        A = np.mod(np.matmul(A, A), self.p).astype(np.int64)
        n >>= 1
    return B

3、矩阵快速幂应用：

3.1三步问题

https://leetcode-cn.com/problems/three-steps-problem-lcci/solution/mei-ri-suan-fa-day-80-suo-you-ren-du-hui-zuo-de-ru/

有个小孩正在上楼梯，楼梯有 nn 阶台阶，小孩一次可以上1 阶、2阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import numpy as np

class Solution:
    def mat_pow(self, A, n):
        m = A.shape[0]
        B = np.eye(m, dtype=np.int64)
        while n > 0:
            if (n&1)!=0:
                B = np.mod(np.matmul(B, A), self.p).astype(np.int64)
            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)
            n >>= 1
        return B;

    def waysToStep(self, n: int) -> int:
        self.p = int(1e9+7)
        f = [1, 2, 4]
        if n <= 3: return f[n-1]
        A = np.array([[0, 0, 1], [1, 0, 1], [0, 1, 1]], dtype=np.int64)
        B = self.mat_pow(A, n-3)
        res = 0
        for i in range(3):
            res += f[i] * B[i][2]
        return int(res%self.p)

3.2 Fibonacci'sSum

复制代码

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
import numpy as np
class Solution:
    def mat_pow(self, A, n):
        m = A.shape[0]
        B = np.eye(m, dtype=np.int64)
        while n > 0:
            if (n & 1):
                B = np.mod(np.matmul(B,A), self.p).astype(np.int64)
            A = np.mod(np.matmul(A, A), self.p).astype(np.int64)
            n >>= 1
        return B          
        
    def getSum(self, n):
        # write code here
        self.p = int(1e9+7)
        if n == 1: return 1
        if n == 2: return 4
        f = [[4], [3], [2], [1], [1]]
        A = np.array([[1,1,1,1,1], [0,1,1,1,1], [0,0,1,1,1],[0,0,0,1,1],[0,0,0,1,0]], dtype=np.int64)
        B = self.mat_pow(A, n-2)
        res = np.matmul(B, f)
        return int(res[0][0]%self.p)

e = Solution()
print(e.getSum(3))

复制代码

#不使用numpy包
class Solution:
    def MatrixMultiply(self, A, B):
        multiply = []
        # if len(A[0]) != len(B):
        #     raise ValueError
        tmp = [list(row) for row in zip(*B)]
        for Al in range(len(A)):
            row =[]
            for Bl in range(len(tmp)):
                num = 0   
                for Br in range(len(tmp[0])):
                    num +=  int((A[Al][Br] * tmp[Bl][Br])%self.p)
                row.append(num)
            multiply.append(row)
        return multiply

def mat_pow(self, A, n):
        m = len(A)
        B = [[1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]]
        while n > 0:
            if (n & 1):
                B = self.MatrixMultiply(B,A)
            A = self.MatrixMultiply(A, A)
            n >>= 1
        return B          
        
    def getSum(self, n):
        # write code here
        self.p = int(1e9+7)
        if n == 1: return 1
        if n == 2: return 4
        f = [[4], [3], [2], [1], [1]]
        A = [[1,1,1,1,1], [0,1,1,1,1], [0,0,1,1,1],[0,0,0,1,1],[0,0,0,1,0]]
        B = self.mat_pow(A, n-2)
        res = self.MatrixMultiply(B, f)
        return int(res[0][0]%self.p)

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
27
28
29
30
31
32
33
34
35
36
37
#不使用numpy包
class Solution:
    def MatrixMultiply(self, A, B):
        multiply = []
        # if len(A[0]) != len(B):
        #     raise ValueError
        tmp = [list(row) for row in zip(*B)]
        for Al in range(len(A)):
            row =[]
            for Bl in range(len(tmp)):
                num = 0   
                for Br in range(len(tmp[0])):
                    num +=  int((A[Al][Br] * tmp[Bl][Br])%self.p)
                row.append(num)
            multiply.append(row)
        return multiply

    def mat_pow(self, A, n):
        m = len(A)
        B = [[1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]]
        while n > 0:
            if (n & 1):
                B = self.MatrixMultiply(B,A)
            A = self.MatrixMultiply(A, A)
            n >>= 1
        return B          
        
    def getSum(self, n):
        # write code here
        self.p = int(1e9+7)
        if n == 1: return 1
        if n == 2: return 4
        f = [[4], [3], [2], [1], [1]]
        A = [[1,1,1,1,1], [0,1,1,1,1], [0,0,1,1,1],[0,0,0,1,1],[0,0,0,1,0]]
        B = self.mat_pow(A, n-2)
        res = self.MatrixMultiply(B, f)
        return int(res[0][0]%self.p)