题目地址：http://poj.org/problem?id=3070
求后四位，还有求前四位的用公式
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <sstream>
#include <vector>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define REPD(i,a,b) for(int i=a;i>=(int)b;i--)
struct Matrix{ int a[2][2]; int r; // r*r Matrix(int r):r(r){memset(a,0,sizeof(a));} //初始化长 void MakeI(int x){ //变为x*E的单位矩阵 memset(a,0,sizeof(a)); for(int i=0;i<r;i++) a[i][i]=x; } Matrix operator * (const Matrix& m) { //矩阵乘法 Matrix result(r); for(int i=0;i<r;i++) for(int j=0;j<r;j++) { for(int k=0;k<r;k++) result.a[i][j]+=a[i][k]*m.a[k][j]; } return result; } Matrix operator % (const int p){ //矩阵对每个元素取余 Matrix result(*this); for(int i=0;i<r;i++) for(int j=0;j<r;j++) result.a[i][j]%=p; return result; } Matrix operator + (const Matrix& m){ //矩阵互相相加 Matrix result(r); for(int i=0;i<r;i++) for(int j=0;j<r;j++) result.a[i][j]=a[i][j]+m.a[i][j]; return result; } Matrix operator + (int n){ //加上个常数 Matrix result(r); result.MakeI(n); return *this+result; }
};
Matrix PowMod(Matrix x,int n,int p) //x^n 对Max取模
{Matrix result(2);result.MakeI(1);Matrix base = x%p; while(n>0){if(n & 1)result=(result*base)%p; //当二进制不为0时，就要乘个 base=(base*base)%p; //累乘此时二进制的权值 n>>=1;}return result;
}
int main()
{Matrix m(2);m.a[0][0]=1;m.a[0][1]=1;m.a[1][0]=1;m.a[1][1]=0;int n;while(scanf("%d",&n)==1&&n!=-1){if(n==0) printf("0\n");else {Matrix ans=PowMod(m,n,10000);printf("%d\n", ans.a[0][1]);}}return 0;
}