3070 Fibonacci 矩阵快速幂

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int m=10000;

int fib(int n)
{
    int t[2][2]={1,1,1,0};
    int p[2][2];
    int a[2][2]={1,0,0,1};
    int i,j,k;
    while(n)
    {
        if(n%2==1)
        {
            for(i=0;i<2;i++)
                for(j=0;j<2;j++)
            {
                p[i][j]=a[i][j]%m;
                a[i][j]=0;
            }
            for(i=0;i<2;i++)
                for(j=0;j<2;j++)
                    for(k=0;k<2;k++)
                        a[i][j]=a[i][j]+p[i][k]*t[k][j];
        }

        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
        {
            p[i][j]=t[i][j]%m;
            t[i][j]=0;
        }

        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                for(k=0;k<2;k++)
                    t[i][j]=(t[i][j]+p[i][k]*p[k][j])%m;
        n=n>>1;
    }
    return a[0][1];
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n==-1) break;
        printf("%d
",fib(n)%m);
    }
    return 0;
}