Hoj 2060 Fibonacci Proble Again

テーマリンク:http://acm.hit.edu.cn/hoj/problem/view?id=2060
Fibsとを求めます.
f[n]=f[n-1]+f[n-2]です.
マトリックス乗算を使うと簡単に分かります.
f[n]=[0 1
           1)
この行列のn-1乗、そしてこの二次元行列の左下と右下の値を加算すればいいです.
本題に対して、私達はsigma(f[i])を求めます.0<=i<=n
我々は、次のように観察することができる.
F(3)=F(1)+F(2) 
F(4)=F(2)+F(3)=1*F(1)+2*F(2) 
F(5)=F(3)+F(4)=2*F(1)+3*F(2)
 F(6)=F(4)+F(5)=3*F(1)+5*F(2)
 F(7)=F(5)+F(6)=5*F(1)+8*F(2)
 F(8)=F(6)+F(7)=8*F(1)+13*F(2) 
S(3)=2*F(1)+2*F(2) 
S(4)=3*F(1)+4*F(2) 
S(5)=5*F(1)+7*F(2)
 S(6)=8*F(1)+12*F(2) 
S(7)=13*F(1)+20*F(2)  発見は難しくないです.S(n)=F(n+2)-F(2)  したがって、テーマはF(b＋2)-F(a＋2-1)を求めるために変換されます.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

#define MOD 1000000000
#define MATRIX_SIZE 3
struct Matrix
{
   long long int elem[MATRIX_SIZE][MATRIX_SIZE];
   int size;
   Matrix(){memset(elem,0,sizeof(elem));}
   void setSize(int _size)
   {
      size = _size;
   }
   Matrix operator = (const Matrix & other)
   {
      setSize(other.size);
      for(int i=0;i<size;i++)
      {
         for(int j= 0;j<size;j++)
         {
            elem[i][j] = other.elem[i][j];
         }
      }
      return *this;
   }
   Matrix operator * (const Matrix & other)
   {
      Matrix temp;
      temp.setSize(size);
      for(int i=0;i<size;i++)
      {
         for(int j=0;j<size;j++)
         {
            for(int k=0;k<size;k++)
            {
               temp.elem[i][j] += elem[i][k] * other.elem[k][j];
               if(temp.elem[i][j]>=MOD) temp.elem[i][j] %= MOD;
            }
         }
      }
      return temp;
   }
   void Power(int exp)
   {
      Matrix E;
      E.setSize(size);
      for(int i=0;i<size;i++) E.elem[i][i] = 1;
      while(exp)
      {
         if(exp & 1) E = E * (*this);
         *this = (*this) * (*this);
         exp >>= 1;
      }
      *this = E;
   }
};

Matrix m;
void init()
{
   m.setSize(2);
   memset(m.elem,0,sizeof(m.elem));
   m.elem[0][1] = 1;m.elem[1][0] = 1;m.elem[1][1] = 1;
}
//S(n) = f(n+2) - f(2) + f(0) = f(n+2) - 1
int main()
{
   #ifndef ONLINE_JUDGE
      freopen("in.txt","r",stdin);
   #endif
   int a,b;
   int sa,sb;
   while(scanf(" %d %d",&a,&b)!=EOF)
   {
      if(a == 0 && b == 0 ) break;
      init();
      m.Power(b+1);
      sb = (m.elem[1][0] + m.elem[1][1] - 1)%MOD;
      init();
      m.Power(a);
      sa = (m.elem[1][0] + m.elem[1][1] - 1)%MOD;
      printf("%d
", (sb-sa + MOD)%MOD);
   }
   return 0;
}