C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2023-03-11 10:46:56

#include <bits/stdc++.h>

using namespace std;

#define out(x) cout << #x << '=' << x << endl
#define out2(x, y) cout << #x << '=' << x << ',' << #y << '=' << y << endl 
#define no cout << "No" << endl; return
#define yes cout << "Yes" << endl; return
#define outvec(a) for (int v : a) { cout << v << ' '; } cout << endl
#define lowbit(x) (x & -x)
#define gcd __gcd 
#define inf 0x3f3f3f3f3f3f3f3fLL
#define infi 0x3f3f3f3f

using ll = long long;
using pii = pair<int, int>;

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

void solve() {
	ll n;
	cin >> n;
	
	cout << fib(n + 1).first << endl;
}




int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    
    while (t--) {
		solve();
	}
}

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2021-02-08 14:43:48

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=1e9+7;
struct mat{
    int a[2][2];
    mat(){memset(a,0,sizeof(a));}
    int *operator [](int x){return a[x];}
    mat operator * (mat b){
	mat c;
	for(int i=0;i<2;++i)
	    for(int j=0;j<2;++j)
		for(int k=0;k<2;++k)
		    c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
	return c;
    }
}S,T;
int main(){
    int kase;
    scanf("%d",&kase);
    while(kase--){
	long long n;
	scanf("%lld",&n);
	T[0][0]=0;T[0][1]=T[1][0]=T[1][1]=1;
	S[0][0]=S[0][1]=1;S[1][0]=S[1][1]=0;
	while(n){
	    if(n&1)S=S*T;
	    T=T*T;
	    n>>=1;
	}
	printf("%d\n",S[0][0]);
    }
}