60pts求助
查看原帖
60pts求助
746849
zhang_Jimmy卡线王楼主2024/3/17 14:06
#include <bits/stdc++.h>
using namespace std;
#define maxn 2
const int mod = 1e9+7;

struct matrix{
	long long a[2][2];
}; 

matrix multi(matrix m1, matrix m2){
	matrix result;
	for(int i = 0; i < maxn; i ++)
		for(int j = 0; j < maxn; j ++){
			result.a[i][j] = (m1.a[i][0]  % mod * m2.a[0][j] % mod % mod + m1.a[i][1] % mod * m2.a[1][j] % mod % mod) % mod;
		}
	return result;
}

matrix s;

matrix quickpow(matrix s, int n){
	if(n == 1) return s;
	if(n & 1){
		matrix p = quickpow(s, n / 2);
		matrix t = multi(p, p);
		return multi(t, s); 
	}
	else{
		matrix p = quickpow(s, n / 2);
		return multi(p, p); 
	}
}

int main(){
	int n;
	s.a[0][0] = 0;
	s.a[0][1] = 1;
	s.a[1][0] = 1;
	s.a[1][1] = 1;
	cin >> n;
	matrix t = quickpow(s, n - 2);
	matrix q;
	q.a[0][0] = 1;
	q.a[0][1] = 1;
	matrix ans = multi(q, t); 
	cout << ans.a[0][1] % mod;
	return 0;
}

2024/3/17 14:06
加载中...