李华

用户名：2645479600

访问量：18660

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1127

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：921

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1574

你可能喜欢

蓝桥杯2014年第五届真题-斐波那契-题解(C语言代码)---C语言---数列求和公式+矩阵快速幂

　　作者: 李华　　　　发表时间：2020-03-29 23:57:39 浏览：2117　|　评论：2　

原题链接：蓝桥杯2014年第五届真题-斐波那契

解题思路:
1.看题目数据高达10^18次方可以知道暴力没有办法做出来，哪怕是O(N)的时间复杂度也会超时，所以需要想办法优化，求斐波那契数列高项的某些信息，首先想到矩阵快速幂
快速幂算法链接：[快速幂算法](https://blog.csdn.net/qq_19782019/article/details/85621386 "快速幂算法")
然后将快速幂算法转换为矩阵快速幂
矩阵　｜1 1｜＾ｎ　对应着斐波那契数列的｜f(n+1)　f(n)　｜
　　　｜0 1｜　　　　　　　　　　　　　｜ｆ(n)　ｆ(n-1)｜

2.斐波那契数列有一个求和公式，就是Sn=f(n+2)-1。所以我们的思路就是求出第n+2项就可以做出这道题了。下面是求和公式推导过程![](/image_editor_upload/20200329114657_58941.jpg)
3.下面是解题的思路
![](/image_editor_upload/20200329114842_29311.jpg)
4.有疑问可以私信或者评论，如果有错误请大家指出。
```c
#include <stdio.h>
#include <string.h>
typedef long long ll;
typedef struct	//矩阵结构体 
{
	ll a[2][2];
}matrix;
ll n,m,p;
ll fib_m; 
ll mul_mod(ll a,ll b,ll p)	//大数相乘取模
{
	ll ans=0;
    while(b)
    {
	    if(b&1)
	    {
	    	ans=ans+a;
	    	ans=ans%p; 
	    }
	    a=a<<1;
	    a=a%p;
	    b=b>>1;
    }
    return ans;
} 
matrix mul_mat_1(matrix first,matrix second)	//矩阵乘法 
{
	matrix result; 
	memset(result.a,0,sizeof(result.a));	//初始化
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				result.a[i][j]=(result.a[i][j]%p+mul_mod(first.a[i][k],second.a[k][j],p)%p)%p;
			}
		}
	} 
	return result;
}
matrix POW_1(matrix mat,ll n)	//矩阵mat的n次方 
{
	matrix t;
	t.a[0][0]=1;	//单位矩阵 
	t.a[0][1]=0;
	t.a[1][0]=0;
	t.a[1][1]=1;
	while(n>0)	//快速幂
	{
		if(n&1)	//如果是奇数
		{
			t=mul_mat_1(t,mat);	//等于结果乘当前的底数 
		} 
		n=n>>1;
		mat=mul_mat_1(mat,mat);	//自身平方 
	} 
	return t;
}
ll quick_fib_1(ll c)	//c代表次方数
{
	matrix mat,temp;
	memset(mat.a,0,sizeof(mat.a));
	mat.a[0][0]=1;
	mat.a[0][1]=1;
	mat.a[1][0]=1;
	temp=POW_1(mat,c);
	return temp.a[0][1];
}
matrix mul_mat(matrix first,matrix second)	//矩阵乘法 
{
	matrix result;
	memset(result.a,0,sizeof(result.a));	//初始化
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				result.a[i][j]=(result.a[i][j]+first.a[i][k]*second.a[k][j]);
			}
		}
	} 
	return result;
}
matrix POW(matrix mat,ll n)	//矩阵mat的n次方 
{
	matrix t;
	t.a[0][0]=1;	//单位矩阵 
	t.a[0][1]=0;
	t.a[1][0]=0;
	t.a[1][1]=1;
	while(n>0)	//快速幂
	{
		if(n&1)	//如果是奇数
		{
			t=mul_mat(t,mat);	//等于结果乘当前的底数 
		} 
		n=n>>1;
		mat=mul_mat(mat,mat);	//自身平方 
	} 
	return t;
}
ll quick_fib(ll c)	//c代表次方数
{
	ll ans;
	matrix mat,temp;
	memset(mat.a,0,sizeof(mat.a));
	mat.a[0][0]=1;
	mat.a[0][1]=1;
	mat.a[1][0]=1;
	temp=POW(mat,c);
	return temp.a[0][1];
}
int main()
{
	scanf("%lld %lld %lld",&n,&m,&p);
	if(m>n+2)	//如果m大于n+2，不需要计算f(m)的值 
	{
		printf("%lld",(quick_fib_1(n+2))%p-1);//可以中途模p 
		return 0;
	}
	else	//否则需要模上f(m) 
	{
		fib_m=quick_fib(m);	//算出fibm的值。这个数没办法取模，只能硬算 
		printf("%lld",(quick_fib(n+2))%fib_m%p-1);//第m项可以不优化求出来 ，所以第n+2项也可以不取模优化 
	}
	return 0;
}
```

0.0分

33 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

哈哈

解题思路的矩阵写错了，然后没有考虑到m，p为1的情况

2022-08-05 20:08:44

李达

very good!

2020-07-26 20:13:34

李华

TA的其他文章

你可能喜欢

校门外的树（C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求素数问题（C语言代码）

C二级辅导-分段函数（C语言代码）

【作业调度方案】（C语言代码）

蓝桥杯2014年第五届真题-斐波那契-题解(C语言代码)---C语言---数列求和公式+矩阵快速幂

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

K-进制数（C++代码）

大神老白（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

兰顿蚂蚁（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

完数（C语言代码）

李华

TA的其他文章

你可能喜欢

校门外的树 （C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求素数问题 （C语言代码）

C二级辅导-分段函数 （C语言代码）

【作业调度方案】 （C语言代码）

蓝桥杯2014年第五届真题-斐波那契-题解(C语言代码)---C语言---数列求和公式+矩阵快速幂

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

K-进制数 （C++代码）

大神老白 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

兰顿蚂蚁 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

完数 （C语言代码）

校门外的树（C++代码）

C语言训练-求素数问题（C语言代码）

C二级辅导-分段函数（C语言代码）

【作业调度方案】（C语言代码）

　　评论区

K-进制数（C++代码）

大神老白（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

兰顿蚂蚁（C++代码）

完数（C语言代码）