POJ 3070 矩阵快速乘幂
/*很水的矩阵题，没什么说的... */#include<iostream>#include<cstdio>#include<cmath>using namespace std;struct matrix{ long long a[3][3];}A,B;matrix mult2(matrix A,matrix B){ /// 矩阵乘法 matrix C; for(int i=1;i<=2;i++){ /// 第一个矩阵的行 for(int j=1;j<=2;j++){ /// 第二个矩阵的列 C.a[i][j]=0; for(int k=1;k<=2;k++){ /// 第二个矩阵的行 或者 第一个矩阵的列 C.a[i][j] = (C.a[i][j] + A.a[i][k]*B.a[k][j])%10000; } } } return C;}matrix mult(matrix A,long long n){ /// 二分快速幂 if(n==1) return A; A = mult(A,n/2); if(n%2==0) return A = mult2(A,A); return A = mult2(mult2(A,A),B);}int main(){ long long n; while(scanf("%lld",&n)!=EOF){ if(!n) { printf("0\n"); continue; } if(n == -1) break; A.a[1][1]=1; A.a[1][2]=1; A.a[2][1]=1; A.a[2][2]=0; B = A; A = mult(A,n); printf("%lld\n",A.a[1][2]%10000); }}