Fshl0

Fibonacci

Feb 8th, 2021
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll Fib (ll n) {
  2.    if (n == 0) return 0;
  3.    if (n == 1 || n == 2)
  4.         return F[n] = 1;
  5.     if (F.count(n)) return F[n];
  6.     ll k = (n % 2) ? ((n + 1) / 2) : (n / 2);
  7.     if (n % 2) return F[n] = (bp (Fib(k), 2) + bp (Fib(k - 1), 2)) % MOD;
  8.     return F[n] = (((2 * Fib (k - 1) + Fib (k)) % MOD) * Fib (k)) % MOD;
  9. }
RAW Paste Data