题目大意：求

Fibonacci Numbers如果位数低于8位，则全部输出，否则只输出

前4位与后4位（注意后四位的0别忘记了，不过是什么格式，哪怕

0000都要输出）；

题目分析：这里我们上一篇文章以前具体阐述了：

给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
由 于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、 A^3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。

然后我们以前有一篇文章已经阐述了，如果利用取对数求第N个fibonacci数的前4位有效数字；如果不清楚的话 请看我以前的一篇文章

“HDU 1568（非常经典微妙的 斐波纳契计算）“

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int sim[50]={0};
double f=(1+sqrt(5.0))/2;
double ff=(1-sqrt(5.0))/2;
struct M{
	int s[5][5];
};
int solve_f4(int n){
	double t=(-0.5)*log(5.0)/log(10.0)+(double(n))*log(f)/log(10.0);
	double k=t-floor(t);
	t=pow(10.0,k);
	while(t<1000)
		t*=10.0;
	return (int)t;
}
struct M multiply(struct M a,struct M b){
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%10000)%10000;
	return c;
}
struct M paw(struct M a,int t){
	if(t==1)
		return a;
	else{
		struct M k=paw(a,t/2);
		if(t&1){
			return multiply(multiply(k,k),a);
		}
		else
			return multiply(k,k);
	}
}
int main(){
	int n,k1,k2;
	struct M a,b;
	a.s[1][1]=1;
	a.s[1][2]=0;
	a.s[2][1]=0;
	a.s[2][2]=1;
	b.s[1][1]=b.s[1][2]=b.s[2][1]=1;
	b.s[2][2]=0;
	sim[0]=0;
	sim[1]=1; sim[2]=1; sim[3]=2;
	for(int i=4;i<=49;i++)
		sim[i]=sim[i-2]+sim[i-1];
	while(scanf("%d",&n)!=EOF){
		if(n<=39){
			printf("%d\n",sim[n]);
			continue;
                     //其实我最初是用公式求前39个fibonacci数的
                     //但是发现有误差，所以改用数组直接模拟出来
		}
		else{
			k1=solve_f4(n);
			struct M k=paw(b,n-1);
			k=multiply(k,a);
			k2=k.s[1][1]%10000;
			printf("%d...%04d\n",k1,k2);
		}
	}
	return 0;
}

”