行列で高速なっち

行列を使うとフィボナッチ数は

で計算できるので、前もってn=1,2,4,8,..2^kについて行列を計算しておけば、結構な速度で求められるようだ。まあ、Cだとオーバーフローを気にせなイカンのであまり使えなさそうだが(;´д｀)

int p[30][4]={{1,1,1,0}};
mul(int*a,int*x,int*y)
{
  int t[4];
  // 32bitだと下4桁程度しか無理そう(´ω｀)
  t[0] = (x[0]*y[0] + x[1]*y[2]) % 10000;
  t[1] = (x[0]*y[1] + x[1]*y[3]) % 10000;
  t[2] = (x[2]*y[0] + x[3]*y[2]) % 10000;
  t[3] = (x[2]*y[1] + x[3]*y[3]) % 10000;

  memcpy(a,t,sizeof(t));
}

main ()
{
  int i,n;

  for(i=1;i<30;i++)
    mul(p[i],p[i-1],p[i-1]);

  for(;~scanf("%d",&n);){
    int k[4]={ 1, 0, 0, 1 };

    for(i=0;i<30;i++)
    {
      if(n & (1<<i))mul(k,k,p[i]);
    }
    printf("%d\n",k[1]);
  }
}