记录编号	122526	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-09-23 21:56:44	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <ctime>
using namespace std;
const long long MOD=1000000007;
struct square
{
  unsigned long long num[3][3];
  square()
  {
    memset(this->num,0,sizeof(this->num));
  }
  square operator *(square &i) const
  {
    square k;
    square j=*this;
    k.num[1][1]=((j.num[1][1]%MOD*i.num[1][1]%MOD)+(j.num[1][2]%MOD*i.num[2][1]%MOD))%MOD;
    k.num[1][2]=((j.num[1][1]%MOD*i.num[1][2]%MOD)+(j.num[1][2]%MOD*i.num[2][2]%MOD))%MOD;
    k.num[2][1]=((j.num[2][1]%MOD*i.num[1][1]%MOD)+(j.num[2][2]%MOD*i.num[2][1]%MOD))%MOD;
    k.num[2][2]=((j.num[2][1]%MOD*i.num[1][2]%MOD)+(j.num[2][2]%MOD*i.num[2][2]%MOD))%MOD;
    return k;
  }
};
square ZERO;
square ONE;
square quickpow(square i,long long  e);
int main()
{  
  long long n;
  freopen("fibsqr.in","r",stdin);
  freopen("fibsqr.out","w",stdout);
  ZERO.num[1][1]=ZERO.num[2][2]=1;ZERO.num[1][2]=ZERO.num[2][1]=0;
  ONE.num[1][1]=ONE.num[1][2]=ONE.num[2][1]=1;ONE.num[2][2]=0;
  scanf("%lld",&n);
    square ans=quickpow(ONE,n);
    cout<<((long long)ans.num[2][1]%MOD*ans.num[1][1]%MOD)%MOD<<endl;
  return 0;
}
square quickpow(square i,long long e)
{ 
   if (e==1)
     return ONE;
   if (e==0)
     return ZERO;
   square half=quickpow(i,e/2);
   half=half*half;
   if (e%2==1)
     half=half*ONE;
   return half;
}