pku 3070題目要求計(jì)算Fibonacci數(shù)列的第n項(xiàng)最后4位。因?yàn)閚可以很大(0 ≤
n ≤ 1,000,000,000)。因此直接計(jì)算在時(shí)限內(nèi)是不可能的（有多個(gè)case）。題目還給出了計(jì)算的方法：表示成矩陣連乘的形式為
這就給我們提供了快速算法，因?yàn)榫仃囅喑藵M足結(jié)合律。預(yù)先計(jì)算上面一個(gè)矩陣的2的冪次方，再將n表示成2進(jìn)制。如當(dāng)n=5時(shí)，只需計(jì)算一次矩陣乘法：1次方乘以4次方。當(dāng)n=1000000000時(shí)最多只需計(jì)算29次矩陣乘法2^29 = 536870912），而且由于矩陣只是2階，計(jì)算量大大減少。
// pku 3070 求fabonacci數(shù)列的快速算法
/*
化為以下矩陣連乘的形式
|F(n+1) F(n) | |1 1|(n)
|F(n) F(n-1)|=|1 0|
將n表示成2進(jìn)制, 矩陣的二進(jìn)制的積可以預(yù)先保存
只需計(jì)算結(jié)果的后4位
*/
#include <iostream>
using namespace std;
int m[31][4]; // 保存29個(gè)2階矩陣
long fact[31];// 2的k次方
void cal()
{
// 單位矩陣
//m[0][0]=1,m[0][1]=0,m[0][2]=0,m[0][3]=1;
m[1][0]=1,m[1][1]=1,m[1][2]=1,m[1][3]=0;
//fact[0]=1;
fact[1]=1;
for(int i=2;i<=30;i++)
{
m[i][0]=(m[i-1][0]*m[i-1][0]+m[i-1][1]*m[i-1][2])%10000;
m[i][1]=(m[i-1][0]*m[i-1][1]+m[i-1][1]*m[i-1][3])%10000;
m[i][2]=(m[i-1][2]*m[i-1][0]+m[i-1][3]*m[i-1][2])%10000;
m[i][3]=(m[i-1][2]*m[i-1][1]+m[i-1][3]*m[i-1][3])%10000;
fact[i]=2*fact[i-1];
}
}
void solve(long n)
{
// 對(duì)n表示成2進(jìn)制
int e[31];
memset(e,0,sizeof(e));
int i,j;
for(i=30;i>=1;i--)
{
if(n>=fact[i])
{
e[i]=1;
n-=fact[i];
}
}
//for(i=1;i<=30;i++) printf("%d\n",e[i]);
// 結(jié)果矩陣，初始時(shí)為單位矩陣
int res[4]={1,0,0,1},tmp[4];
for(i=1;i<=30;i++)
{
if(e[i]!=0)
{
tmp[0]=(res[0]*m[i][0]+res[1]*m[i][2])%10000;
tmp[1]=(res[0]*m[i][1]+res[1]*m[i][3])%10000;
tmp[2]=(res[2]*m[i][0]+res[3]*m[i][2])%10000;
tmp[3]=(res[2]*m[i][1]+res[3]*m[i][3])%10000;
for(j=0;j<4;j++) res[j]=tmp[j];
}
}
printf("%d\n",res[1]);
}
int main()
{
cal();
long n;
while(scanf("%ld",&n) && n>=0)
{
solve(n);
}
return 1;
}