【51Nod】1242 - 斐波那契数列的第N项（矩阵快速幂）

FishWang

发布于 2025-08-27 10:58:39

8300

代码可运行

运行总次数：0

代码可运行

点击打开题目

1242 斐波那契数列的第N项

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

斐波那契数列的定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)

给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。

Input

输入1个数n(1 <= n <= 10^18)。

Output

输出F(n) % 1000000009的结果。

Input示例

Output示例

斐波那契数列矩阵递推公式：

跑一个矩阵快速幂就行了。注意数据类型。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct Matrix
{
	int w,h;
	LL m[3][3];
}ori,ans;
const LL mod = 1000000009;
void init()
{
	ans.w = ans.h = 2;
	ans.m[1][1] = ans.m[2][2] = 1;
	ans.m[1][2] = ans.m[2][1] = 0;
	ori.w = ori.h = 2;
	ori.m[1][1] = ori.m[1][2] = ori.m[2][1] = 1;
	ori.m[2][2] = 0;
}
Matrix Matrix_mul(Matrix a,Matrix b)
{
	Matrix t;
	t.h = a.h;
	t.w = b.w;
	CLR(t.m,0);
	for (int i = 1 ; i <= a.h ; i++)
	{
		for (int j = 1 ; j <= a.w ; j++)
		{
			if (a.m[i][j] == 0)
				continue;
			for (int k = 1 ; k <= b.w ; k++)
				t.m[i][k] = (t.m[i][k] + a.m[i][j] * b.m[j][k] % mod) % mod;
		}
	}
	return t;
}
void quick_mod(LL n)
{
	while (n)
	{
		if (n & 1)
			ans = Matrix_mul(ori , ans);
		ori = Matrix_mul(ori , ori);
		n >>= 1;
	}
}
int main()
{
	LL n;
	init();
	scanf ("%lld",&n);
	quick_mod(n);
	printf ("%lld\n",ans.m[1][2] % mod);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

matrix