pku 3070题目要求计算Fibonacci数列的第n项最后4位。因为n可以很大(0 ≤
n ≤ 1,000,000,000)。因此直接计算在时限内是不可能的（有多个case）。题目还给出了计算的方法：表示成矩阵连乘的形式为
这就给我们提供了快速算法，因为矩阵相乘满足结合律。预先计算上面一个矩阵的2的幂次方，再将n表示成2进制。如当n=5时，只需计算一次矩阵乘法：1次方乘以4次方。当n=1000000000时最多只需计算29次矩阵乘法2^29 = 536870912），而且由于矩阵只是2阶，计算量大大减少。
// pku 3070 求fabonacci数列的快速算法
/*
化为以下矩阵连乘的形式
|F(n+1) F(n) | |1 1|(n)
|F(n) F(n-1)|=|1 0|
将n表示成2进制, 矩阵的二进制的积可以预先保存
只需计算结果的后4位
*/
#include <iostream>
using namespace std;
int m[31][4]; // 保存29个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)
{
// 对n表示成2进制
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]);
// 结果矩阵，初始时为单位矩阵
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;
}