题目链接：

id=3070

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

结果保留四位数字。

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

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

#include
     
      #include
      
       #include
       
        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