seq/famous/fibonacci.hpp

• View this file on GitHub
• Last update: 2023-02-28 19:11:49+09:00
• Include: #include "seq/famous/fibonacci.hpp"

Verified with

• test/3_yukicoder/303.test.cpp

Code

// 0, 1, 1, 2, 3, 5, ...
template <typename mint>
mint fibonacci(ll N) {
  using P = pair<mint, mint>;
  P f = {0, 1}, res = {1, 0};
  while (N) {
    auto& [a, b] = f;
    auto& [c, d] = res;
    if (N & 1) { res = {a * c + b * d, b * c + (a + b) * d}; }
    f = {a * a + b * b, b * (a + a + b)};
    N >>= 1;
  }
  return res.se;
}

#line 1 "seq/famous/fibonacci.hpp"
// 0, 1, 1, 2, 3, 5, ...
template <typename mint>
mint fibonacci(ll N) {
  using P = pair<mint, mint>;
  P f = {0, 1}, res = {1, 0};
  while (N) {
    auto& [a, b] = f;
    auto& [c, d] = res;
    if (N & 1) { res = {a * c + b * d, b * c + (a + b) * d}; }
    f = {a * a + b * b, b * (a + a + b)};
    N >>= 1;
  }
  return res.se;
}

Back to top page