矩阵快速幂

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。

给定整数n，求Fibnmod10000Fibnmod10000。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含一个整数n。

当输入用例n=-1时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围

0≤n≤2∗1090≤n≤2∗109

输入样例：

0
9
999999999
1000000000
-1

输出样例：

0
34
626
6875

代码;

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int mod  = 10000;
int mul(int f[2],int a[2][2])
{
    int c[2];
    memset(c,0,sizeof(c));
    for(int j=0;j<2;j++)
    {
        for(int k=0;k<2;k++)
        c[j] = (c[j]+(ll) f[k]*a[k][j])%mod;
    }
    memcpy(f,c,sizeof(c));
}
int mulself(int a[2][2])
{
    int c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                c[i][j] = (c[i][j] + (ll)a[i][k]*a[k][j])%mod;
            }
        }
    }
    memcpy(a,c,sizeof(c));
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n!=-1)
    {
        int f[2]={0,1};
        int a[2][2] ={{0,1},{1,1}};
        for(;n;n>>=1)
        {
            if(n&1)mul(f,a);
            mulself(a);
        }
        cout << f[0] << endl;
    }
    return 0;
}