Fibonacci hoj 矩阵快速幂裸题

#include <stdio.h>#include <cstring>const int mod=10000;int A[3][3],ans[3][3];void mul(int a[][3],int b[][3]){    int tmp[3][3];    for(int i=1; i<=2; i++)        for(int j=1; j<=2; j++)        {            tmp[i][j]=0;            for(int k=1; k<=2; k++)            {                tmp[i][j]+=a[i][k]*b[k][j];            }            if(tmp[i][j]>=mod) tmp[i][j]%=mod;        }    memcpy(a,tmp,sizeof(tmp));}void pow(int a[][3],int b[][3],int n){    int tmp[3][3];    memcpy(tmp,b,sizeof(int)*9);    a[1][1]=a[2][2]=1;    a[1][2]=a[2][1]=0;    while(n)    {        if(n&1)        mul(a,tmp);        mul(tmp,tmp);        n>>=1;    }}int main(){    int n;    while(scanf("%d",&n)==1)    {        if(n==-1) break;        A[1][1]=A[1][2]=A[2][1]=1;        A[2][2]=0;        pow(ans,A,n);        printf("%d\n",ans[1][2]);    }    return 0;}