洛谷P1962 斐波那契数列 (矩阵快速幂)

题目链接：https://www.luogu.com.cn/problem/P1962

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int M = 1000000007;

ll n, m; 

struct Matrix{
	int a[2][2];
	
	Matrix(){
		memset(a, 0, sizeof(a)); 
	}
	
	void build(){
		for(int i = 0 ; i < 2 ; ++i) a[i][i] = 1;
	}
	
	Matrix operator * (const Matrix &B) const{
		Matrix res;
		int r;
		for(int i = 0 ; i < 2 ; ++i){
			for(int k = 0 ; k < 2 ; ++k){
				r = a[i][k];
				for(int j = 0 ; j < 2 ; ++j){
					res.a[i][j] = (res.a[i][j] + 1ll * r * B.a[k][j] % M) % M;
				}
			}
		}
		return res;
	}
};

Matrix qsm(Matrix i, ll po){
	Matrix res; res.build();

	while(po){
		if(po & 1) res = res * i;
		po >>= 1;
		i = i * i;
	}

	return res;
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	n = read();
	
	if(n <= 2){
		printf("%d
", 1);
	} else{
	Matrix ans, base;
	ans.a[0][0] = ans.a[0][1] = 1;
	base.a[0][0] = 1, base.a[0][1] = 1, base.a[1][0] = 1, base.a[1][1] = 0;
	
	ans = ans * qsm(base, n - 2);

	printf("%d
", ans.a[0][0] % M);
	}	
	return 0;
}