51Nod-1537-分解（矩阵快速幂）

博主链接

题目链接

题意：

给一个n，求出对应m满足（1+sqrt(2))^n==sqrt(m)+sqrt(m-1)

题解：

可以将（1+sqrt(2))^n一项项拆开后发现
sqrt(1)+sqrt(2)
sqrt(9)+sqrt(8)
sqrt(49)+sqrt(50)
sqrt(492+9)+sqrt(492+10)
发现如果n为奇数f(n)=f(n-2)+2f(n-1)+1;
为偶数时f(n)=f(n-2)+2f(n-1);
所以可以推出状态转移矩阵
2 1
1 0

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int N = 1e9+7;
void Matrix(ll(&a)[2][2], ll b[2][2]) {
	ll tmp[2][2] = { 0 };
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % N;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			a[i][j] = tmp[i][j];
		}
	}
}
int main() {
	ll n;
	scanf("%lld", &n);
	int flag = n % 2;
	ll temp[2][2] = { 2,1,1,0 }, cot[2][2] = { 1,0,0,1 }, x[2] = { 3, 1 };   //f(n)=2*f(n-1)+f(n-2) if(n%2) ans=f(n)*f(n)+1 else ans=f(n)*f(n)
	if (n == 1) {
		cout << 2 << endl;
		return 0;
	}
	n -= 2;
	while (n) {
		if (n & 1)Matrix(cot, temp);
		Matrix(temp, temp);
		n /= 2;
	}
	ll ans = 0;
	for (int i = 0; i < 2; i++)ans = (ans + x[i] * cot[0][i]) % N;
	ans = (ans%N)*(ans%N)%N;
	if (flag) ans+=1;
	printf("%lld\n", ans);
	return 0;
}