Fibonacci

题意：求斐波那契的第n项，0<=n<=1e9

思路：设f[n][2]为一个1*2的矩阵，表示斐波那契的第n项和第n+1项{fib[n],fib[n+1]}，那么求它的下一项就是乘一个2*2的矩阵

{01}

{11}然后就是矩阵快速幂做就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e4;
#define ll long long
void 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));
}

void 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);
        }
        printf("%d\n",f[0]);
    }
}