求斐波那切数列的几个方法：

经典做法：

众所周知：斐波那契数列的定义是f(n + 1) = f(n) + f(n - 1)
我们有两种方式来实现：一个是递归，一个是动态规划

递推：

int dfs(int n)
{
   
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	return dfs01(n - 1) + dfs01(n - 2);
}

动态规划

int dfs03(int n)
{
   
	vec[maxn]
	vec[0] = 1;
	vec[1] = 2;
	int i;
	for (i = 2; i < n; i++)
	{
   
		vec[i] = vec[i - 1] + vec[i - 2];
	}
	return vec[i-1];
}

矩阵快速幂

经典做法只要数一大就会超时，我们可以用矩阵快速幂进行优化，能将时间复杂度降到O(logN)
（如果全位输出斐波那契数，貌似最大能算法到93，但是如果带mod，那就可以算很大）
常用于求第n位斐波那契数的后x位（mod 10^x）

原理：

快速幂+矩阵
矩阵乘法：左矩阵的第一行乘以右矩阵的第一列（分别相乘），乘完后相加
单位矩阵： nn的矩阵 mat ( i , i )=1; 任何一个矩阵乘以单位矩阵就是它本身 n单位矩阵=n， 可以把单位矩阵等价为整数1。（单位矩阵用在矩阵快速幂中）

在斐波那契数列中：
f[n ] = 1 * f[n-1] + 1 * f [n - 2]
f[n-1] =1 * f[n-1] +0 * f [n - 2]
我们用矩阵来表示：

这就表示了斐波那契数列如何用矩阵来实现。

代码：

#include <iostream> 
#include <cstddef> 
#include <cstring> 
#include <vector> 
using namespace std;  
typedef long long ll;  
const int mod=10000;  
typedef vector<ll> vec;  
typedef vector<vec> mat;  
mat mul(mat &a,mat &b) 
{
     
    mat c(a.size(),vec(b[0].size()));  
    for(int i=0; i<2; i++)  
    {
     
        for(int j=0; j<2; j++)  
        {
     
            for(int k=0; k<2; k++)  
            {
     
                c[i][j]+=a[i][k]*b[k][j];  
                c[i][j]%=mod;  
            }  
        }  
    }  
    return c;  
}  
mat pow(mat a,ll n)  
{
     
    mat res(a.size(),vec(a.size()));  
    for(int i=0; i<a.size(); i++)  
        res[i][i]=1;//单位矩阵； 
    while(n)  
    {
     
        if(n&1) res=mul(res,a);  
        a=mul(a,a);  
        n/=2;  
    }  
    return res;  
}  
ll solve(ll n)  
{
     
    mat a(2,vec(2));  
    a[0][0]=1;  
    a[0][1]=1;  
    a[1][0]=1;  
    a[1][1]=0;  
    a=pow(a,n);  
    return a[0][1];//也可以是a[1][0]; 
}  
int main()  
{
     
    ll n;  
    while(cin>>n&&n!=-1)  
    {
     
        cout<<solve(n)<<endl;  
    }  
    return 0;  
}  

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;   
struct  matrix      //定义结构体矩阵
{
   
    ll x[2][2];
} ;
matrix  mul(matrix a,matrix b)     //矩阵乘法运算
{
   
    matrix ans;
    memset(ans.x,0,sizeof(ans.x));
       for(int i=0;i<2;i++)          //三个循环表示两个方阵相乘，可手动推写一遍
       {
   
           for(int j=0;j<2;j++)
           {
   
               for(int k=0;k<2;k++)
               {
   
                   ans.x[i][j]+=a.x[i][k]*b.x[k][j];
                   ans.x[i][j]%=mod;
               }
           }
       }
       return ans;
}
matrix quickpow(matrix p,ll n)    //矩阵快速幂，与快速幂道理方法相同
{
   
    matrix ans;
    for(int i=0;i<2;i++)
    {
   
        for(int j=0;j<2;j++)
        {
   
            if(i==j){
   ans.x[i][j]=1;}   //一开始初始化他为单位阵
            else ans.x[i][j]=0;
        }
    }
    while(n)//快速幂
    {
   
        if(n&1)
        {
   
           ans=mul(ans,p);
        }
        p=mul(p,p);
        n>>=1;
    }
    return ans;
}
int main()
{
   
    matrix m;
    m={
   0,1,1,1};      
    ll n;
    cin>>n;
    ll ans1=0;
    matrix ans=quickpow(m,n-1);

    cout<<ans.x[1][1]<<endl;    
    return 0;  
}

例题：

POJ 3070

模拟过程

如果数很大，比如求1000的斐波那契数列，矩阵快速幂也求不出来,那咋办?
我们可以模拟斐波那契数列数列计算的过程，斐波那契数列的定义是f(n + 1) = f(n) + f(n - 1)，我们可以手写加减，模拟进行加减运算
例题 大菲波数
H DU - 1715

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
int main(){
   
    int n,q,i,j,temp=0;
    cin>>q;
    while(q--)
    {
   
    	cin>>n;
    	  char a[10010]="1",b[10010]="1",c[10010]={
   0};
	    for(i=0;i<n-2;i++){
   
	        int len=max(strlen(a),strlen(b));
	        for(j=0;j<len;j++){
      //模拟加法
	            temp=0;
	            if(a[j]>='0'){
       //短的数不加
	                temp+=a[j]-'0';
	            }
	            if(b[j]>='0'){
   
	                temp+=b[j]-'0';
	            }
	            if(temp>=10){
         //判断进位
	                if(c[j]>='0'){
   
	                    c[j]+=temp-10;
	                }
	                else{
   
	                    c[j]+=temp-10+'0';
	                }
	                c[j+1]=1+'0';
	            }
	            else{
   
	                if(c[j]>='0'){
   
	                    if(temp==9){
      //若前位进位了,而且加上的数字是9,那么还要进位!!!
	                        c[j]='0';
	                        c[j+1]='1';
	                    }
	                    else{
   
	                        c[j]+=temp;
	                    }
	                }
	                else{
   
	                    c[j]+=temp+'0';
	                }
	            }
	        }
	        strcpy(a, b);
	        strcpy(b, c);
	        memset(c, 0, sizeof(c));
	    }
	    int len=strlen(b);
	    for(i=len-1;i>=0;i--){
     //倒着输出
	        printf("%c",b[i]);
	    }
	    printf("\n");
	}
  

    return 0;
}