[HDU3117]Fibonacci Numbers

题目：Fibonacci Numbers

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3117

分析：

1）后四位可以用矩阵快速幂解决。$T= \left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right] $

2）前四位：Fibonacci公式：$ans= \frac{1}{\sqrt{5}} * { ( {\frac{1+sqrt{5}}{2}}^n – {\frac{1-\sqrt{5}}{2}}^n )}$

当n够大时，${( \frac{1-\sqrt{5}}{2} )}^n$趋于0。

取以10为底的对数：

$log_{10}{ans} = log_{10}{\frac{1}{\sqrt{5}} * {[ {\frac{1+sqrt{5}}{2}}^n – {\frac{1-\sqrt{5}}{2}}^n ]}}$

$= log_{10}{\frac{1}{\sqrt{5}} * {[ \frac{1+sqrt{5}}{2} ]}^n }$

$= log_{10}{\frac{1}{\sqrt{5}} + log_{10}{\frac{1+sqrt{5}}{2}}^n}$

$= -0.5*log_{10}{5} + n*log_{10}{[ \frac{1+sqrt{5}}{2} ]}$

然后

$10^{ans} \% 10000$=$10^{[ans]} * 1000$=$10^{3+ans-(long long)ans}$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int MOD=;
struct Matrix{
    LL a[][];
    void init(int f){
        memset(a,,sizeof a);
        if(f==-)return;
        for(int i=;i<;++i)a[i][i]=;
    }
};
Matrix operator*(Matrix& A,Matrix& B){
    Matrix C;C.init(-);
    for(int i=;i<;++i)
    for(int j=;j<;++j)
        for(int k=;k<;++k){
            C.a[i][j]+=A.a[i][k]*B.a[k][j];
            C.a[i][j]%=MOD;
        }
    return C;
}
Matrix operator^(Matrix A,int n){
    Matrix Rt;Rt.init();
    for(;n;n>>=){
        if(n&)Rt=Rt*A;
        A=A*A;
    }
    return Rt;
}
int main(){
    Matrix A,T;
    T.a[][]=;T.a[][]=;
    T.a[][]=;T.a[][]=;
    for(int n;~scanf("%d",&n);){
        if(n<){
            A=T^n;
            printf("%lld\n",A.a[][]);
        }else{
            A=T^n;
            double ans=-0.5*log10(5.0)+n*log10((+sqrt(5.0))/);
            ans=ans-(LL)ans+;
            printf("%d...%04lld\n",(int)pow(,ans),A.a[][]%);
        }
    }
    return ;
}