#2 Tìm số fibonanci thứ N trong O(logN*log(logN))

[nasia2003]

Chứng minh công thức tổng quát theo phương trình toán học:

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const ll MOD = 1e9+7;
 
map <ll, ll> F;
ll fibo(int n)
{
    if(F.count(n)) return F[n];
    int t = n/2;
    if(n & 1) return F[n] = (fibo(t)*fibo(t + 1) + fibo(t - 1)*fibo(t)) % MOD;
    else return F[n] = (fibo(t)*fibo(t) + fibo(t - 1)*fibo(t - 1)) % MOD;
}
 
int main()
{
    ll n = 2000000000;
    F[1] = F[1] = 1;
    cout << (n == 0 ? 0 : fibo(n - 1)) << '\n';
}