题目

题目描述

求数列 \(f_n=f_{n-2}+f_{n-1}\) 的前 \(n\) 项的和，其中 \(f_1=1,f_2=1\)。
输出的数 \(\bmod\ 10^9+7\)

样例

样例输入

10

样例输出

143

数据范围

对于 \(20\%\) 的数据，有 \(1\leq n\leq 20\)

对于 \(100\%\) 的数据，有 \(1≤n<2^{63}\)

分析

这道题目矩阵乘法的经典应用，矩阵乘法经常与快速幂结合在一起，难点在于将矩阵的前n项构造出来，因为这道题目需要求解的是前n项的和，所以可以将前n项和s放入到矩阵中，这样可以在矩阵乘法中计算出s。令

\(F_{n} = \left [ F_{n} , F_{n+1} , S_{n} \right ]\)

\(F_{n+1} = \left [ F_{n+1} , F_{n+2} , S_{n+1} \right ]\)

可以构造出对应的矩阵A，可以根据下面的式子计算矩阵乘法。

$\left [ F_{n} , F_{n+1} , S_{n} \right ] \cdot \begin{bmatrix} 0 & 1 & 0 \ 1 & 1 & 1 \ 0 & 0 & 1\end{bmatrix} = \left [ F_{n+1} , F_{n+2} , S_{n+1} \right ] \left ( F_{n}\cdot A = F_{n+1} \right ) $

$\to A = \begin{bmatrix} 0 & 1 & 0 \ 1 & 1 & 1 \ 0 & 0 & 1\end{bmatrix} , F_{n} = F_{1} \cdot A_{n-1} , F_{1} = \left [ 1 , 1 , 1 \right ] , res = F_{n}\left [ 2 \right ] $

code

from typing import List
 
 
class Solution:
    # 矩阵乘法满足结合律所以可以使用快速幂来解决
    # res = res * a
    def mul(self, n: int, mod: int, a: List[int], b: List[List[int]]):
        temp = [0] * n
        for i in range(n):
            for j in range(n):
                temp[i] = (temp[i] + a[j] * b[j][i]) % mod
        # 将结果复制到原来的a中, a其实是f1
        for i in range(n):
            a[i] = temp[i]
 
    # a = a * a
    def mul2(self, n: int, mod: int, a: List[List[int]], b: List[List[int]]):
        temp = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % mod
        for i in range(n):
            for j in range(n):
                a[i][j] = temp[i][j]
 
    def process(self):
        n, m = map(int, input().split())
        # 将前n项和存储到矩阵中, f1的第三个元素存储的是前n项的和
        f1 = [1, 1, 1]
        a = [[0, 1, 0], [1, 1, 1], [0, 0, 1]]
        # 因为是从A1开始的所以计算的其实是A ^ (n - 1)
        n -= 1
        while n > 0:
            # res = res * a
            if n & 1:
                self.mul(3, m, f1, a)
            self.mul2(3, m, a, a)
            n >>= 1
        return f1[2]
 
 
if __name__ == '__main__':
    print(Solution().process())