这道题其实也是水题来的，求Fibonacci数的前4位和后4位，在n==40这里分界开。后4位不难求，因为n达到了10^18的规模，所以只能用矩阵快速幂来求了，但在输出后4位的时候一定要注意前导0的处理（我就是在这里wa了一发，也是看了看别人的代码才发现的）。
前4位的话稍微有点难处理，我一开始就在想该怎么处理 log10(f(n)) 呢？把f[n]= f[n-1]+f[n-2]? 不行，log对+运算没法展开，我找了好久也没能找到什么能让f[n]展开成相乘或者幂的形式，上网搜了下题解，才发现别人竟然是用通项公式来处理的（我当时也想过，但因为含有"-"运算所以就直接忽略了，可是没想到其实可以稍微变通下就可以把"-"号去掉的）： f(n)= 1/sqrt(5) (( (1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n );
具体实现的时候Log10 F[n]约等于 ((1+sqrt(5))/2)^n/sqrt(5)，这里我们把 ((1-sqrt(5))/2)^n这一项忽略了，因为当N>=40时，这个数已经小的可以忽略。于是log10 F[n]就可以化简成 n*log10( (1+sqrt(5))/2 ) -log10 sqrt(5)，不多说，附上代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#define For(i,s,t) for(int i=s; i<=t; ++i)
typedef long long LL;
const LL mod= ; struct matrix{
LL a,b,c,d;
matrix(LL a=, LL b=, LL c=, LL d=):a(a),b(b),c(c),d(d) {}
matrix operator *(const matrix &m2) const {
return matrix((a*m2.a%mod+b*m2.c%mod)%mod, (a*m2.b%mod+b*m2.d%mod)%mod, (c*m2.a%mod+d*m2.c%mod)%mod, (c*m2.b%mod+d*m2.d%mod)%mod);
}
} A(,,,),E(,,,); matrix quick_mod(matrix m, LL b){
matrix res(E);
while(b){
if(b&) res= res*m;
m= m*m;
b>>=;
}
return res;
} void solve(LL n){
LL last= quick_mod(A,n-).a;
// int last= int(quick_mod(A,n-1).a);
double m= n*log10((+sqrt(5.0))/)-log10(sqrt(5.0));
m -= LL(m);
LL first= LL(pow(10.0,m)*);
//一定要有04d！后4位的前导0也要输出！
printf("%I64d...%04I64d\n",first,last);
} LL f[]= {,,};
void init(int n=){
For(i,,n) f[i]= f[i-]+f[i-];
} int main(){
init();
LL n;
while(~scanf("%I64d",&n)){
if(n<) printf("%I64d\n",f[n]);
else solve(n);
}
return ;
}
很神奇的是，用 I64d来输出前4位竟然是0ms（直接%04d的话却是15ms），好像第一次排上了hdu榜上的第一页，哈哈~~附上一张图：