数学问题之（矩阵加速递推快速幂）

P1962 斐波那契数列
题目描述
大家都知道，斐波那契数列是满足如下性质的一个数列：
Fn =1  (n <=2) 
Fn =F(n-1)+F(n-2)  (n>=3) 
请你求出 Fn mod 10^9 + 7  的值。
输入格式
一行一个正整数 n
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
5
样例输出 #1
5
样例 #2
样例输入 #2
10
样例输出 #2
55
提示
【数据范围】    
对于 60% 的数据，1<= n <= 92；   
对于 100% 的数据，1<= n < 2^63。

//示例代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=1e9+7;
struct matrix{//矩阵结构体
	LL c[3][3];
	matrix(){memset(c,0,sizeof(c));}//初始化矩阵
}A,res;
LL n;
matrix operator*(matrix &a,matrix &b){//原算符重载 *
	matrix t;
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)//矩阵乘法
				t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%M;
	return t;
}
void quickpow(LL n){//快速幂
	A.c[1][1]=A.c[1][2]=A.c[2][1]=1;//初始化A矩阵
	res.c[1][1]=res.c[1][2]=1;//初始化单位矩阵
	while(n){
		if(n&1) res=res*A;
		A=A*A;
		n>>=1;
	}
}
int main()
{
	scanf("%lld",&n);
	if(n<3){printf("1");return 0;}
	quickpow(n-2);//运算
	printf("%lld",res.c[1][1]);
	return 0;
}

#示例代码 Python版

# -*- coding:utf-8 -*-
import numpy as np
M=10**9+7
base=np.array([1,1],dtype=np.int64)
a=np.array([[1,1],[1,0]],dtype=np.uint64)
n=int(input())
if n<=2:
    print(1)
else:
    k=n-2
    res=np.array([[1,0],[0,1]],dtype=np.int64)
    while k>0:
        if k&1:
            res=(np.matmul(res,a)%M).astype(np.int64)
        a= (np.matmul(a,a)%M).astype(np.int64)
        k>>=1
    base = (np.matmul(base,res)%M).astype(np.int64)
    print(base[0])

最后

以上就是害怕小丸子为你收集整理的数学问题之（矩阵加速递推快速幂）的全部内容，希望文章能够帮你解决数学问题之（矩阵加速递推快速幂）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。