斐波那契数列后四位可以用快速幂取模(模10000)算出。前四位要用公式推

f(n)=(((1+√5)/2)^n+((1-√5)/2)^n)/√5

假设F[n]可以表示成 t * 10^k（t是一个小数），那么对于F[n]取对数log₁₀，答案就为log₁₀ t + K，此时很明显log₁₀ t<1，于是我们去除整数部分，就得到了log₁₀ t 

再用pow（10，log₁₀ t)我们就还原回了t。将t×1000就得到了F[n]的前四位。 具体实现的时候Log10 F[n]约等于((1+√5)/2)^n/√5，这里我们把((1-√5)/2)^n这一项忽略了，

因为当N>=40时，这个数已经小的可以忽略。于是log₁₀ F[n]就可以化简成log₁₀ 1/√5 + n*log₁₀ (1+√5)/2

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int Mod = 10000;const int N = 4;int msize;struct Mat{    int mat[N][N];};Mat operator *(Mat a, Mat b){    Mat c;    memset(c.mat, 0, sizeof(c.mat));    for(int k = 0; k < msize; ++k)        for(int i = 0; i < msize; ++i)            if(a.mat[i][k])                for(int j = 0; j < msize; ++j)                    if(b.mat[k][j])                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;    return c;}Mat operator ^(Mat a, int k){    Mat c;    memset(c.mat,0,sizeof(c.mat));    for(int i = 0; i < msize; ++i)        c.mat[i][i]=1;    for(; k; k >>= 1)    {        if(k&1) c = c*a;        a = a*a;    }    return c;}int a[50];const double sq5 = sqrt(5.0);int main(){//    freopen("in.txt","r",stdin);    int n;    msize = 2;    Mat A;    A.mat[0][0] = 1;    A.mat[0][1] = 1;    A.mat[1][0] = 1;    A.mat[1][1] = 0;    a[0] = 0;    a[1] = 1;    for(int i=2;i<40;i++)        a[i] = a[i-1] + a[i-2];    while(~scanf("%d", &n))    {        if(n<40) printf("%d\n",a[n]);        else        {            double t = n * log10((1.0 + sq5) / 2) - log10(sq5);            t -= (int)t;            t = pow(10.0, t);            printf("%d...",(int)(t * 1000));            Mat aa = A;            aa = aa ^ (n-1);            printf("%04d\n",aa.mat[0][0]);        }    }    return 0;}