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;}