比赛 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(){;}