记录编号	283064	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2016-07-14 07:54:50	内存使用	0.32 MiB

#include <bits/stdc++.h>
using namespace std;
 
unsigned long long n, p;
struct Matrix{
	unsigned long long n, m, a[5][5];//琛 鍒
	void clear()
	{
		n = m = 0;
		memset(a, 0, sizeof(a));
	} 
	
	Matrix operator * (const Matrix& x) const {//鐭╅樀涔樻硶 
		Matrix tmp;
		tmp.clear();
		tmp.n = n;
		tmp.m = x.m;
		for(int i = 1; i <= tmp.n; i++){
			for(int j = 1; j <= tmp.m; j++){
				for(int k = 1; k <= m; k++){
					tmp.a[i][j] += a[i][k] * x.a[k][j];
					tmp.a[i][j] %= 1000000007;
				}
			}
		}
		return tmp;	
	}
	
	Matrix operator + (const Matrix& x) const {//鐭╅樀鍔犳硶
		Matrix tmp;
		tmp.clear();
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= m; j++)
				tmp.a[i][j] = a[i][j] + x.a[i][j];
		return tmp;
	}
 
};
 
int main()
{
	freopen("fibsqr.in", "r", stdin);freopen("fibsqr.out", "w", stdout);
	scanf("%llu", &n);
	if(n == 0){
		puts("0");
		return 0;
	}	
	Matrix first, x; 
	first.clear(); x.clear();
	first.n = 1; first.m = 2;
	first.a[1][1] = 1, first.a[1][2] = 0;
	x.n = 2; x.m = 2;
	x.a[1][1] = 1; x.a[1][2] = 1; x.a[2][1] = 1; x.a[2][2] = 0;	
	for(unsigned long long i = 1; i <= n; i <<= 1, x = x * x){
		if(n & i)	first = first * x;
	}
	printf("%llu\n", first.a[1][1]%1000000007 * first.a[1][2]%1000000007);
	//printf("%lf", (double)clock()/CLOCKS_PER_SEC);
	//system("pause");
	fclose(stdin);
	fclose(stdout);
	return 0;
}