记录编号	428078	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-07-24 15:47:22	内存使用	0.29 MiB

#include<cstdio>
#include<cctype>
const long long mod=1000000007;
using namespace std;
inline long long get();
inline long long solve();
long long n;
long long fib[5]={0,0,1,0,0},coe[5][5];
int main()
{
	freopen("fibsqr.in","r",stdin);
	freopen("fibsqr.out","w",stdout);
	n=get()-1;
	coe[1][1]=1;coe[1][2]=1;coe[1][3]=2;coe[1][4]=1;
	coe[2][1]=0;coe[2][2]=1;coe[2][3]=2;coe[2][4]=1;
	coe[3][1]=0;coe[3][2]=1;coe[3][3]=1;coe[3][4]=0;
	coe[4][1]=0;coe[4][2]=1;coe[4][3]=0;coe[4][4]=0;
	printf("%lld",solve()+1);
	return 0;
}
inline long long solve()
{
	while(n)
	{
		if(!(n%2))
		{
			long long temp[5][5];
			for(int i=1;i<=4;i++)
			{
				for(int j=1;j<=4;j++)
				{
					temp[i][j]=0;
					for(int k=1;k<=4;k++)
					{
						temp[i][j]=(temp[i][j]+coe[i][k]*coe[k][j])%mod;
					}
				}
			}
			for(int i=1;i<=4;i++)
			{
				for(int j=1;j<=4;j++)
				{
					coe[i][j]=temp[i][j];
				}
			}
			n>>=1;
		}
		long long temp[5];
		for(int i=1;i<=4;i++)
		{
			temp[i]=0;
			for(int j=1;j<=4;j++)
			{
				temp[i]=(temp[i]+coe[i][j]*fib[j])%mod;
			}
		}
		for(int i=1;i<=4;i++)fib[i]=temp[i];
		n--;
	}
	return fib[1]%mod;
}
inline long long get()
{
	long long t=0,j=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}