o(n)的算法是铁定会t的，这里使用矩阵快速幂可以将时间复杂度降到O(logn)

斐波那契数列的定义

数学归纳法推一下式子

啥时候能编辑latex捏

AC代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
const int mod=1000000007;

typedef vector<ll> vec;
typedef vector<vec> mat;

mat mul(mat A,mat B)
{
	mat C(A.size(),vec(B[0].size()));
	for(int i=0;i<A.size();i++)
		for(int j=0;j<B.size();j++)
			for(int k=0;k<B[0].size();k++)
				C[i][k]=(C[i][k]+A[i][j]*B[j][k]%mod)%mod;
	return C;
}
mat pow(mat A,ll n)
{
	mat B(A.size(),vec(A.size()));
	for(int i=0;i<A.size();i++)
		B[i][i]=1; 
	while(n)
	{
		if(n&1) B=mul(B,A);
		A = mul(A,A);
		n >>= 1; 
	}
	return B;
}
 
int main()
{
	ll n;
	cin >> n;
	mat A(2, vec(2));
	A[0][0] = 1; A[0][1] = 1;
	A[1][0] = 1; A[1][1] = 0;
	A = pow(A, n);
	printf( "%lld\n", A[1][0] );
	return 0;
}