记录编号 |
458159 |
评测结果 |
AAAAAAAAAA |
题目名称 |
斐波那契平方和 |
最终得分 |
100 |
用户昵称 |
CSU_Turkey |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.003 s |
提交时间 |
2017-10-10 14:51:33 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include<bits/stdc++.h>//听说结构体会漂亮点qwq
#define ll long long//好像还是很丑啊
using namespace std;//1,0,0,1这个矩阵乘任何矩阵都等于矩阵本身,相当于自然数1
const int mod=1e9+7;
ll n,ans=1;
struct square{
ll a[3][3];
square(){}
square(ll x,ll y,ll z,ll o){
a[1][1]=x;a[1][2]=y;a[2][1]=z;a[2][2]=o;
}
square operator * (const square &o)const{
return square(a[1][1]*o.a[1][1]%mod+a[1][2]*o.a[2][1]%mod,a[1][1]*o.a[1][2]%mod+a[1][2]*o.a[2][2]%mod,a[2][1]*o.a[1][1]%mod+a[2][2]*o.a[2][1]%mod,a[2][1]*o.a[1][2]%mod+a[2][2]*o.a[2][2]%mod);
}
}a,b;
void fast(ll x){
while(x){
if(x&1)b=b*a;a=a*a;x>>=1;
}ans=ans*b.a[1][1]%mod*(b.a[2][1]+b.a[1][1])%mod;
}
int main()
{
freopen("fibsqr.in","r",stdin);freopen("fibsqr.out","w",stdout);
scanf("%lld",&n);
if(!n){
cout<<0;return 0;
}
a=square(1,1,1,0);b=square(1,0,0,1);
fast(n-1);cout<<ans;
return 0;
}