C++14(g++5.4) 解法, 执行用时: 117ms, 内存消耗: 2724K, 提交时间: 2020-08-05 21:03:02

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
int T;
long long n;
struct mat{
	int a[3][3];
}u;
mat matmul(mat x,mat y){
	mat tmp;
	for(int i=1;i<3;i++)
		for(int j=1;j<3;j++){
			tmp.a[i][j]=0;
			for(int k=1;k<3;k++)tmp.a[i][j]=(tmp.a[i][j]+1LL*x.a[i][k]*y.a[k][j]%mod)%mod;
		}
	return tmp;
}
void matpow(long long b){
	mat rec=u;
	while(b){
		if(b&1)rec=matmul(rec,u);
		u=matmul(u,u);
		b>>=1;
	}
	cout<<(2LL*rec.a[1][1]%mod+rec.a[1][2])%mod<<"\n";
}
int main(){
	Fox;
	cin>>T;
	while(T--){
		cin>>n;
		if(n<=2){
			cout<<n<<"\n";
			continue;
		}
		u.a[1][1]=u.a[1][2]=u.a[2][1]=1;u.a[2][2]=0;
		matpow(n-3);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 261ms, 内存消耗: 1312K, 提交时间: 2023-03-15 09:09:31

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

#define int long long
const int mod = 1e9 + 7;

pair<int, int> fib(int n) {
    if (n == 0) return {0, 1};
    auto p = fib(n >> 1);
    int c = p.first * (2 * p.second - p.first);
    int d = p.first * p.first + p.second * p.second;
    if (n & 1)
        return {(d % mod + mod) % mod, ((c + d) % mod + mod) % mod};
    else
        return {(c % mod + mod) % mod, (d % mod + mod) % mod};
}

signed main()
{
    int t;
    cin >> t;
    while (t --)
    {
        int n;
        cin >> n;
        cout << fib(n).second << endl;
    }
    return 0;
}