矩阵十大经典标题之五- poj-3070-Fibonacci
矩阵十大经典题目之五- poj-3070-Fibonacci
题目很简单。
注意初始化,一开始没有初始化,然后就错了。悲伤。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define Nnum 31 #define Mnum 31 #define LL long long struct matrix { int mat[3][3]; matrix() { memset(mat,0,sizeof(mat)); } }; matrix mul(matrix A,matrix B) { matrix C; int i,j,k; for(i=1; i<=2; i++) { for(j=1; j<=2; j++) { for(k=1; k<=2; k++) { C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%10000; } } } return C; } matrix powmul(matrix A,int k) { matrix B; B.mat[1][1]=B.mat[2][2]=1; while(k>=1) { if(k&1)B=mul(B,A); A=mul(A,A); k=k/2; } return B; } int main() { int n; matrix A; while(~scanf("%d",&n)&&(n+1)) { A.mat[1][1]=A.mat[1][2]=A.mat[2][1]=1; A.mat[2][2]=0; A=powmul(A,n); cout<<A.mat[1][2]<<endl; } return 0; }