比赛 |
201712练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
斐波那契平方和 |
最终得分 |
100 |
用户昵称 |
サイタマ |
运行时间 |
0.002 s |
代码语言 |
C++ |
内存使用 |
0.32 MiB |
提交时间 |
2018-01-07 09:56:36 |
显示代码纯文本
#include<fstream>
#define MOD 1000000007
using namespace std;
ifstream cin("fibsqr.in");
ofstream cout("fibsqr.out");
long long ans,q,w,e,r,n,x1,x2,x3,x4,y11,y2,y3,y4;
int lyh()
{
cin>>n;n--;
x1=1;
x2=0;
x3=0;
x4=1;
y11=1;
y2=1;
y3=1;
y4=0;
while(n)
{
if(n&1)
{
q=x1*y11+x2*y3;
w=x1*y2+x2*y4;
e=x3*y11+x4*y3;
r=x3*y2+x4*y4;
x1=q%MOD;x2=w%MOD;x3=e%MOD;x4=r%MOD;
}
n>>=1;
q=y11*y11+y2*y3;
w=y11*y2+y2*y4;
e=y3*y11+y4*y3;
r=y3*y2+y4*y4;
y11=q%MOD;y2=w%MOD;y3=e%MOD;y4=r%MOD;
}
ans=((x1+x2)%MOD)*((x3+x4)%MOD)%MOD;
cout<<ans<<endl;
cin.close();
cout.close();
return 0;
}
int Main=lyh();
int main(){;}