摘要
Title: 1303. 斐波那契前 n 项和
Tag: 斐波那契、矩阵快速幂、快速倍增法
Memory Limit: 64 MB
Time Limit: 1000 ms

1303. 斐波那契前 n 项和

题意

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。
现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Sn mod m。
思路

求斐波那契的几种方法：Link
- 方法1
  矩阵快速幂 复杂度 $O(logN)$
  
  用来构造矩阵，求特殊值
- 方法2
  快速倍增法 复杂度 $O(logN)$
  
  用来求斐波那契的第 $n$ 项，这里可以结合斐波那契项和和的关系，来求解
  
  Given $F(k)$ and $F(k+1)$ , we can calculate these:
  $F(2k)=F(k) * [2*F(k+1)-F(k)] \\ F(2k+1)=F(k)^2+F(k+1)^2.$
  定理：
  $S_n = f_{n + 2} - f_{2} = f_{n + 2} - 1$

代码

矩阵快速幂

'''
Author: NEFU AB-IN
Date: 2022-04-04 16:00:36
FilePath: \ACM\Acwing\1303.py
LastEditTime: 2022-04-04 16:43:32
'''
M = 3
Matrix = lambda: [[0] * M for _ in range(M)]


def mul(a, b):
    c = Matrix()
    for i in range(M):
        for j in range(M):
            for k in range(M):
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m
    return c


def quickpow(a, b):
    I = Matrix()  #单位矩阵
    for i in range(M):
        for j in range(M):
            I[i][j] = 1 if i == j else 0
    while b:
        if b & 1:
            I = mul(I, a)
        b >>= 1
        a = mul(a, a)
    return I


n, m = map(int, input().split())

# Fn = [fn, fn+1, Sn]
F1 = [1, 1, 1]
A = [[0, 1, 0], [1, 1, 1], [0, 0, 1]]

B = quickpow(A, n - 1)
ans = F1[0] * B[0][2] + F1[1] * B[1][2] + F1[2] * B[2][2]

print(ans % m)

快速倍增法

'''
Author: NEFU AB-IN
Date: 2022-04-04 17:11:22
FilePath: \ACM\Acwing\1303.1.py
LastEditTime: 2022-04-04 17:17:12
'''


def dfs(x):                             #存的是二元组 [f[x], f[x + 1]]
    if x == 0:
        return [0, 1]
    f = dfs(x >> 1)                     #往下递归
                                        # k 为 上一层的x
    f1 = (f[0] * (2 * f[1] - f[0])) % m #f1 = f(2 * k)
    f2 = (f[0]**2 + f[1]**2) % m        # f2 = f(2 * k + 1)
    if x & 1:                           # 说明 x = 2 * k + 1， 说明 f[x] = f2, f[x - 1] = f1，所以f[x + 1] = f1 + f2  
        return [f2, (f1 + f2) % m] 
    return [f1, f2]                     # 说明 x = 2 * k， 说明 f[x] = f1, f[x + 1] = f2


n, m = map(int, input().split())
print( (dfs(n + 2)[0] - 1) % m )

1303. 斐波那契前 n 项和

题意

思路

代码