IPCP 2005 Northern Preliminary for Northeast North-America &&Fibonacci Numbers


nを数えて、Fibonacci数のn番目の項の前の4項と後の4項を求めさせて、8項のないのは前の4項だけを出力します.
構想:後の4項は求めやすくて、2つの方法、1種はマトリックスを構築して、1種はその周期を求めます.の最初の4つはFibonacci式を使っています
コード:
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
#define  I  (1.0+sqrt(5.0))/2
#define M 10000
using namespace std;
typedef long long L;
typedef struct str
{ L s[2][2];
}Node;
Node a,b,c;
inline void init()
{   a.s[0][0]=0;a.s[0][1]=1;
    a.s[1][0]=1;a.s[1][1]=1;
	b.s[0][0]=1;b.s[0][1]=0;
	b.s[1][0]=0;b.s[1][1]=1;
	c.s[0][0]=1;c.s[0][1]=1;
	c.s[1][0]=0;c.s[1][1]=0;
}
Node ceil(Node p,Node q)
{  Node aa;
   memset(aa.s,0,sizeof(aa.s));
   for(int i=0;i<2;++i)
	   for(int j=0;j<2;++j)
		   for(int t=0;t<2;++t)
			   aa.s[i][j]=(aa.s[i][j]+p.s[i][t]*q.s[t][j])%M;
   return aa;
}
Node doit(int k)
{ 
	Node p=b,q=a;
  while(k)
  { if(1&k) p=ceil(p,q);
       q=ceil(q,q);
	   k=k>>1;
  }
  p=ceil(c,p);//      
  return p;
}
int main()
{ 
	int f[40]={0,1};
   for(int i=2;i<40;++i)
	    f[i]=f[i-1]+f[i-2];
   init();
   int n;
   while(~scanf("%d",&n))
   { 
	   if(n<40)
    { printf("%d
",f[n]); continue; } int k=n-2; Node bb=doit(k); double ans=-0.5*(log10(5.0))+n*log10(I); ans-=(int)ans; ans=pow(10.0,ans); while(ans<1000) ans*=10.0; printf("%d...",(int)ans); printf("%04d
",bb.s[0][1]);// 0 int mm=5; }return 0; }