Compile time Fibonacci

power.cc

#include <cstdio>

#include <array>

using std::array;

const int MOD = 1000;

class ArrayWrapper {
  const array<int, 2>& value;
 public:
  constexpr ArrayWrapper(const array<int, 2>& value): value(value) {}
  constexpr int operator[](int pos) const {
    return value[pos];
  }
};

class Matrix {
  const array<array<int, 2>, 2> values;
 public:
  constexpr Matrix(int a, int b, int c, int d): values{{{{a, b}}, {{c, d}}}} {}
  constexpr ArrayWrapper operator[](int pos) const {
    return values[pos];
  }
};

constexpr Matrix ID(1, 0, 0, 1);

constexpr Matrix operator*(const Matrix& a, const Matrix& b) {
  int res[2][2] = {{0, 0}, {0, 0}};
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        (res[i][j] += a[i][k] * b[k][j]) %= MOD;
      }
    }
  }
  return Matrix(res[0][0], res[0][1], res[1][0], res[1][1]);
}

constexpr Matrix power(const Matrix& a, long long N) {
  if (N == 0) {
    return ID;
  }
  auto half = power(a, N >> 1);
  auto res = half * half;
  return (N & 1) ? res * a : res;
}

template<long long N>
class Wrapper {
 public:
  static const auto value = N;
};

constexpr Matrix m(3, 4, 5, 6);
constexpr Matrix fib(1, 1, 1, 0);
constexpr auto r = fib * fib * fib * fib * fib * fib * fib;
constexpr auto p = power(fib, 1LL << 60);
int main() {
  printf("%lld\n", Wrapper<p[0][0]>::value);
}