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

106 阅读 0 评论 70 点赞

我是靠谱客的博主害怕小丸子，这篇文章主要介绍数学问题之（矩阵加速递推快速幂），现在分享给大家，希望可以做个参考。

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。

复制代码

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
//示例代码
#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;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#示例代码 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])