题目链接：http://poj.org/problem?

id=3070

题目大意：给定n和10000，求第n个Fibonacci数mod 10000 的值，n不超过2^31。

结果保留四位数字。

非常easy的题，和之前做过的相比简单非常多了。

构造最简单的斐波那契数列矩阵。

#include<iostream>

#include<cstring>

#include<stdio.h>

using namespace std;

const int MAX = 2;

struct Matrix

{

    int v[MAX][MAX];

};

int n=2,M=10000;

Matrix mtAdd(Matrix A, Matrix B)        // 求矩阵 A + B

{

    int i, j;

    Matrix C;

    for(i = 0; i < n; i ++)

        for(j = 0; j < n; j ++)

            C.v[i][j]=(A.v[i][j]+B.v[i][j])% M;

    return C;

}

Matrix mtMul(Matrix A, Matrix B)        // 求矩阵 A * B

{

    int i, j, k;

    Matrix C;

    for(i = 0; i < n; i ++)

        for(j = 0; j < n; j ++)

        {

            C.v[i][j] = 0;

            for(k = 0; k < n; k ++)

                C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % M;

        }

    return C;

}

 Matrix mtPow(Matrix origin,int k)  //矩阵高速幂

 {

     int i;

     Matrix res;

     memset(res.v,0,sizeof(res.v));

     for(i=1;i<=n;i++)

         res.v[i][i]=1;

     while(k)

     {

         if(k&1)

             res=mtMul(res,origin);

         origin=mtMul(origin,origin);

         k>>=1;

     }

     return res;

 }

void out(Matrix A)

{

    for(int i=0;i<n;i++)

    {

        for(int j=0;j<n;j++)

        cout<<A.v[i][j]<<" ";

        cout<<endl;

    }

    cout<<endl;

}

Matrix mtCal(Matrix A, int k)    // 求S (k) = A + A2 + A3 + … + Ak

{

    if(k == 1) return A;

    Matrix B = mtPow(A, (k+1) / 2);

    Matrix C = mtCal(A, k / 2);

    if(k % 2 == 0)

        return mtMul(mtAdd(mtPow(A, 0), B), C);   // 如S(6) = (1 + A^3) * S(3)。

    else

        return mtAdd(A, mtMul(mtAdd(A, B), C));   // 如S(7) = A + (A + A^4) * S(3)

}

int main ()

{

    int num;

    while (~scanf("%d",&num))

    {

        if(num==-1) break;

    Matrix A;

    A.v[0][0]=1;

    A.v[0][1]=1;

    A.v[1][0]=1;

    A.v[1][1]=0;

    Matrix ans=mtPow(A,num);

    //out(ans);

    cout<<ans.v[1][0]<<endl;

    }

}