在acm中，经常会遇到特别坑爹的题，就是特别简单的题，但是出题人会把数据范围给的特别大，导致用常规的算法也不出来，比如求1e8范围内的斐波那契数，第一次遇到这个题目时我也是一年懵逼，知直到我遇到了她——矩阵运算+快速幂，简称矩阵快速幂：

举个荔枝：

斐波那契数列的递推公式是F(n)=F(n-1)+F(n-2),按照超贵的算法我们只能递归，然而由于递归深度太深，栈空间和时间肯定都会爆炸的，我们知道在求a的n次方的时候我们就是利用的二分的思想将o(n)的复杂度转化为了o(logn),那么有没有一种方法能够将这种递推公式转化为幂公式呢，这时候就要用的线性代数中的矩阵运算了：

Fn          1  1       *    Fn-1

Fn-1=   1   0            Fn-2

这样就将递推公式转换成幂公式了，我们只需要写出矩阵的加法和乘法运算就可以使用快速幂的算法快速求出第n项斐波那契数列：

先说一下矩阵的基本性质：

1.结合性 （AB)C=A(BC）．

2.对加法的分配性 （A+B)C=AC+BC，C(A+B）=CA+CB ．

3.对数乘的结合性 k(AB）=（kA)B =A(kB）．

4.关于转置 (AB)’=B’A’．

若A为n×k矩阵，B为k×m矩阵，则它们的乘积AB(有时记做A·B)将是一个n×m矩阵。前一个矩阵的列数应该等于后一个矩阵的行数，得出的矩阵行数等于前一个矩阵的行数，列数等于后一个矩阵的行数。

其乘积矩阵AB的第i行第j列的元素为：

一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体

示例代码：

/*
    title:
    description:
    author: averyboy
    time:
    version:
*/
#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;
}