题目链接

新型斐波那契数列

题目描述

新型斐波那契数列的第一、二、三项都为 $1$ ，从第四项起每一项等于前面三项之和，求此数列第 $n$ 项模 $m$ 的余数。

输入描述

输入一行为两个整数 $n$ 、$m$ ，用空格隔开。

输出描述

输出一行为新型斐波那契数列第 $n$ 项模 $m$ 的余数。

输入输出样例

输入

7 3

输出

2

数据范围

• $1⩽n⩽10^{18}$
• $1⩽m⩽100$

解题思路

矩阵快速幂

根据题意，假设这个新型斐波那契数列 $F$ 有 $n$ 项(下标起始为 1 )，那么有如下递推式：
$$F_n=\{\begin{array}{l}1n⩽3\\ F_{n-3}+F_{n-2}+F_{n-1}n>3\end{array}$$
1、动态规划——按照表达式直接递推，时间复杂度为 $O(n)$ 。由于 $n$ 的数据范围较大，会超时。
2、矩阵快速幂
对数列的前几项计算， $F_1=F_2=F_3=1,F_4=3,F_5=5,F_5=9$
矩阵形式：
$$\left[\begin{array}{c}{F}_2\\ F_3\\ F_4\end{array}\right]=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]\cdot \left[\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right]$$
$$\left[\begin{array}{c}{F}_3\\ F_4\\ F_5\end{array}\right]=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]\cdot \left[\begin{array}{c}{F}_2\\ F_3\\ F_4\end{array}\right]$$
于是有$$\left[\begin{array}{c}{F}_3\\ F_4\\ F_5\end{array}\right]={\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]}^2\cdot \left[\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right]$$
将上述情况推广到 $n$项，有$$\left[\begin{array}{c}{F}_{n-2}\\ F_{n-1}\\ F_n\end{array}\right]={\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]}^{n-3}\cdot \left[\begin{array}{c}{F}_1\\ F_2\\ F_3\end{array}\right]$$
记 $3\times 3$大小矩阵 $A$,其中$$A=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]$$

采用矩阵快速幂的方法快速计算出 $F_n$ 的值，由于 $A$ 为固定的 $3\times 3$ 大小，因此复杂度为 $O(\log n)$ 。
输出
1、当输入的 $n$ 小于等于 3 时，可以直接输出 1 返回结果；
2、当输入的 $n$ 大于3 时，利用矩阵快速幂计算出 $A^{n-3}$ ,由于 $F_1=F_2=F_3=1$ ,因此可以直接将 $A^{n-3}$ 的最后一行求和，该结果即为 $F_n$ 。

AC Code

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
import sys
N,M=map(int,input().split())class matrix:def __init__(self,m:list(list())):self.m=mdef __mul__(self,other):         #运算符 * 的重载re=[[0,0,0],[0,0,0],[0,0,0]]for i in range(3):for j in range(3):for k in range(3):re[i][j]=(re[i][j]+self.m[i][k]*other.m[k][j])%Mreturn matrix(re)def pow_matrix(a:matrix,n:int):      #矩阵快速幂ans=matrix([[1,0,0],[0,1,0],[0,0,1]])while n:if n&1:ans=ans*aa=a*an>>=1return ansif N<=3:print(1)sys.exit(0)
bas=matrix([[0,1,0],[0,0,1],[1,1,1]])
res_mat=pow_matrix(bas,N-3)fres=(res_mat.m[2][0]+res_mat.m[2][1]+res_mat.m[2][2])%M
print(fres)