POJ - 3070 Fibonacci（矩阵快速幂）
斐 波 那 契 数 列 第 N 项 斐波那契数列第N项 斐波那契数列第N项
F 0 = 0 , F 1 = 1 , F n = F n ? 1 + F n ? 2 F0 = 0, F1 = 1, Fn = Fn ? 1 + Fn ? 2 F0=0,F1=1,Fn=Fn?1+Fn?2
2 < = n < = 1 , 000 , 000 , 000 2<=n <=1,000,000,000 2<=n<=1,000,000,000
并 且 对 结 果 进 行 10000 取 模 并且对结果进行10000取模 并且对结果进行10000取模
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct Matrix
{
int m[2][2];
};
int n;
Matrix Multi(Matrix b,Matrix c)
{
Matrix res;memset(res.m,0,sizeof res.m);for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)res.m[i][j]=(res.m[i][j]+b.m[i][k]%10000*c.m[k][j]%10000)%10000;return res;
}
int fastpow(Matrix a,int n)
{
Matrix res;memset(res.m,0,sizeof res.m);for(int i=0;i<2;i++) res.m[i][i]=1;while(n){
if(n&1) res=Multi(res,a);a=Multi(a,a);n>>=1;}return res.m[0][1];
}
int main()
{
while(scanf("%d",&n)!=EOF){
if(n==-1) break;Matrix a;memset(a.m,0,sizeof a);a.m[0][0]=1;a.m[0][1]=1;a.m[1][0]=1;printf("%d\n",fastpow(a,n));}return 0;
}