蓝桥杯2014年第五届真题——斐波那契（矩阵快速幂）

1.题目描述
2.输入输出

3.样例输入输出

4.解题思路
思路一：暴力求解
最常规的思路，一看到斐波那契数列就用递归去写，因此可以写一个斐波那契的函数，然后调用函数来写

#include
using namespace std;
int fb(int n){
	if(n==1 || n==2) return 1;
	else return fb(n-1)+fb(n-2);
}
int main(){
	int n,m,p;
	cin>>n>>m>>p;
	long long kount=0;
	for(int i=1;i<=n;i++){
		kount+=fb(i);
	}
	cout< 
很遗憾，这样做在n非常大的时候会超时。因此如果在蓝桥杯中使用递归暴力去求解这题，只能骗到一部分分数，没办法完全ac掉。
 
思路二：矩阵快速幂
 先了解一下快速幂，所谓快速幂，就是快速的求某一个数的多少次幂，其时间复杂度是O（logn），与朴素的O（n）相比，效率得到了极大的提高，它的基本原理是二进制
 快速幂：
 对于a^n ， n一定可以用二进制表示。
 如156（10）=10011100（2）
 求解a^156，原来要进行156-1=155次乘法运算，现在的差不多运算次数就是他 二进制的长度二进制中1的个数=84=24次
 
 
快速幂模板函数
 
long long fastpow(long long x,long long y)
{
    long long a=1;//a为结果
    while(y)
    {
        if(y&1) a=a*x;
        x=x*x;//一个中间转移量. y每右移一次, x 就多一个平方
        y=y>>1;
    }
    return a;
}
 
矩阵快速幂：
 1.相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法运算什么的也遵循矩阵的运算法则。
 2.矩阵快速幂的难点主要是在关系矩阵的构造上，只要关系矩阵构造出来了，其他的就只是套模板运算而已。
 
矩阵
 
struct node {
    int mat[15][15];//定义矩阵 
}x,y;
 
矩阵乘法
 
node mul(node x,node y){//矩阵乘法 
    node tmp;
    for(int i=0;i 
矩阵快速幂
 
node matpow(node x,node y,int num){//矩阵快速幂 
    while(num){
        if(num&1){
            y=mul(y,x);
        }
        x=mul(x,x);
        num=num>>1;
    }
    return y;
}
 
斐波那契数列关系矩阵递推式
 
 本题参考代码（源自网络）
 
#include
#include
using namespace std;
typedef long long LL;
LL llmul( LL a,LL b,LL mod ) {
    a%=mod;a+=mod;a%=mod;
    b%=mod;b+=mod;b%=mod;
    if ( a>n>>m>>mod;
    cout<<( solve( n+2,m,mod )-1+mod )%mod<