以前從沒有對(duì)O（log N）和O（N）的區(qū)別有所正確認(rèn)識(shí)，今日總算知道了。它們的唯一區(qū)別就是，N是一億的時(shí)候，log(N)就是不到26，N還是一億。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3070
PKU的這道題雖然容易，但的確很有意思。我也是第一次用快速冪取模，一用，果然不同凡響。
快速冪取模，其實(shí)就是秦九韶算法 取指數(shù)。
把n化成二進(jìn)制形式后，得到一個(gè)多項(xiàng)式,寫成秦九韶形式，多項(xiàng)式的加就是乘，乘則為指數(shù)運(yùn)算（指數(shù)為2）。由于N的二進(jìn)制位個(gè)數(shù)為log(n),這樣把O（N）的問題化為O（log N）。
.
//PKU 3070 ,calculate Fibonacci
#include <iostream>
#include<stack>
int FPM(int);//fast-power-modulus function declare
using namespace std;
const int Mod=10000;
int main(int argc, char *argv[])
{
int n=0;
while(scanf("%d",&n))
{
if(n==-1)
break;
printf("%d\n",FPM(n));
}
return 0;
}
int FPM(int n)//fast-power-modulus function
{
int matr[4]={1,0,0,1};//initialize matrix
stack<bool>dec;//stack to store binary digit
while(n)//resolve n to binary digit
{
dec.push(1&n);//get the last binary digit
n>>=1;
}
while(!dec.empty())
{
//matrix square
matr[1]=((matr[0]+matr[3])*matr[1])%Mod;
matr[0]=(matr[0]*matr[0]+matr[2]*matr[2])%Mod;
matr[3]=(matr[3]*matr[3]+matr[2]*matr[2])%Mod;
matr[2]=matr[1];
//matrix multiply,
if(dec.top())
{
matr[0]=(matr[0]+matr[1])%Mod;
matr[1]=(matr[1]+matr[3])%Mod;
matr[3]=matr[2];
matr[2]=matr[1];
}
dec.pop();
}
return matr[1];//matr[1] is the result F[N]
}