矩阵快速幂求斐波那契数
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 2;const int mod = 10000;LL n;struct Matx{int mat[maxn][maxn];Matx(){memset(mat,0,sizeof(mat));}};Matx mult(int n1,int m1,Matx mat1,int n2,int m2,Matx mat2){Matx ans;for(int i = 0; i < n1; i++)for(int j = 0; j < m1; j++){for(int k = 0; k < n2;k++){ans.mat[i][j] += mat1.mat[i][k] * mat2.mat[k][j];}ans.mat[i][j] %= mod;}return ans;}void solve(){Matx mat1,mat2;mat1.mat[0][0] = 0;mat1.mat[0][1] = mat1.mat[1][0] = mat1.mat[1][1] = 1;mat2.mat[0][0] = 0;mat2.mat[1][0] = 1;while(n){if(n & 1){mat2 = mult(2,2,mat1,2,1,mat2);}mat1 = mult(2,2,mat1,2,2,mat1);n >>= 1;}printf("%d\n",mat2.mat[1][0]);}int main(){while(cin >> n){if(n == -1)break;if(n > 0){n –;solve();}elseprintf("0\n");}return 0;}
，看着它洗涤一缕缕阳光，看着它映衬一片片星辉，
