@[toc]

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

经典做法：

众所周知：斐波那契数列的定义是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位

原理：

快速幂+矩阵
矩阵乘法：左矩阵的第一行乘以右矩阵的第一列（分别相乘），乘完后相加
单位矩阵： 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;  
}  

例题：

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;
}