#397362 (C++14) No.718 行列のできるフィボナッチ数列道場 (1)

• 問題: No.718 行列のできるフィボナッチ数列道場 (1)
• ユーザー: ​
• 提出日時: 2019-11-10 13:43:53
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,837 bytes
• コンパイル時間: 1,397 ms
• コンパイル使用メモリ: 110,820 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-15 04:57:42
• 合計ジャッジ時間: 2,253 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 20

ソースコード

// #define NDEBUG

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
#include <map>

// [0, max)
#define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var))
// [min, max)
#define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var))
// [min, max)
#define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

// a < b < c
#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
// a <= b < c
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
// a < b <= c
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))
// a <= b <= c
#define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c)))

#ifndef NDEBUG
#  define MASSERT(cond) m_assert(cond, __LINE__, #cond);
#else
#  define MASSERT(...)
#endif

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

using ld = long double;

void m_assert(const bool& cond, const sl& line, const char *condstr) {
  if (!cond) {
    cerr << "Assertion Failed: " << condstr << " at line " << line << endl;
    exit(1);
  }
}

template <class T>
tuple<T, T, T> xgcd(const T& a0, const T& b0) {
  T a = a0, b = b0;
  T x = 0, y = 1, u = 1, v = 0;
  while (a != 0) {
    auto q = b / a;
    auto r = b % a;
    auto m = x - u * q;
    auto n = y - v * q;
    b = a;
    a = r;
    x = u;
    y = v;
    u = m;
    v = n;
  }
  return make_tuple(b, x, y);
}

sl modinv(const sl& a, const sl& m) {
  auto t = xgcd(a, m);
  MASSERT(std::get<0>(t) == 1);
  auto res = std::get<1>(t) % m;
  if (res < 0) {
    res += m;
  }
  res %= m;
  return res;
}

template <class T>
struct Matrix {
  sl N, M;
  vector<vector<T>> mat;

  static Matrix<T> Identity(const sl& N) {
    Matrix<T> ret(N, N);
    FOR0(i, N) {
      ret.mat[i][i] = 1;
    }
    return std::move(ret);
  }

  static Matrix<T> Zero(const sl& N, const sl& M) {
    Matrix<T> ret(N, M);
    return std::move(ret);
  }

  Matrix(const sl& _N, const sl& _M) : N(_N), M(_M) {
    MASSERT(0 < N);
    MASSERT(0 < M);
    mat.resize(N);
    FOR0(i, N) {
      mat[i].resize(M, 0);
    }
  }

  Matrix(const Matrix<T>& _from) : N(_from.N), M(_from.M), mat(_from.mat) {}

  Matrix<T> operator=(const Matrix<T>& _from) {
    N = _from.N;
    M = _from.M;
    mat = _from.mat;
    return *this;
  }

  inline Matrix<T> add(const Matrix<T>& B) const {
    MASSERT(N == B.N);
    MASSERT(M == B.M);
    Matrix<T> ret(*this);
    FOR0(i, N) {
      FOR0(j, M) {
        ret.mat[i][j] += B.mat[i][j];
      }
    }
    return std::move(ret);
  }

  inline Matrix<T> sub(const Matrix<T>& B) const {
    MASSERT(N == B.N);
    MASSERT(M == B.M);
    Matrix<T> ret(*this);
    FOR0(i, N) {
      FOR0(j, M) {
        ret.mat[i][j] -= B.mat[i][j];
      }
    }
    return std::move(ret);
  }

  inline Matrix<T> mult(const Matrix<T>& B) const {
    MASSERT(M == B.N);
    Matrix<T> ret(N, B.M);
    FOR0(i, N) {
      FOR0(k, M) {
        auto mik = mat[i][k];
        FOR0(j, B.M) {
          ret[i][j] += (mik * B[k][j]);
        }
      }
    }
    return std::move(ret);
  }

  inline Matrix<T> power(const sl& x) const {
    MASSERT(0 < x);
    MASSERT(N == M);
    Matrix<T> ret = Matrix<T>::Identity(N);
    Matrix<T> temp = *this;
    sl t = x;
    while (t != 0) {
      if ((t & 1) == 1) {
        ret = ret.mult(temp);
      }
      temp = temp.mult(temp);
      t >>= 1;
    }
    return std::move(ret);
  }

  inline Matrix<T> scalarmult(const T& s) const {
    Matrix<T> ret(*this);
    FOR0(i, N) {
      FOR0(j, M) {
        ret.mat[i][j] *= s;
      }
    }
    return std::move(ret);
  }

  const vector<T>& operator[](const sl& idx) const {
    MASSERT(LELT(0, idx, N));
    return mat[idx];
  }

  vector<T>& operator[](const sl& idx) {
    MASSERT(LELT(0, idx, N));
    return mat[idx];
  }

  inline T determinant(void) const {
    MASSERT(N == M);
    vector<vector<T>> m = mat;
    T ret = 1;
    FOR0(i, N) {
      if (m[i][i] == 0) {
        FOR0(j, N) {
          if (m[j][i] != 0) {
            swap(m[i], m[j]);
            ret = -ret;
            break;
          }
        }
      }
    }
    FOR0(i, N) {
      FORi(j, i + 1, N) {
        auto c = -m[j][i] / m[i][i];
        FORi(k, i + 1, M) {
          m[j][k] += c * m[i][k];
        }
      }
      ret *= m[i][i];
    }
    return std::move(ret);
  }
};

template <sl Mod>
struct Z_over_nZ{
  sl x;

  Z_over_nZ(const sl& _x) : x(_x % Mod) {
    if (x < 0) {
      x += Mod;
    }
  }

  template <class T>
  Z_over_nZ<Mod> operator+=(const T& y) {
    x += y;
    x %= Mod;
    return *this;
  }

  template <class T>
  Z_over_nZ<Mod> operator-=(const T& y) {
    x -= y;
    x %= Mod;
    return *this;
  }

  template <class T>
  Z_over_nZ<Mod> operator*=(const T& y) {
    x *= y;
    x %= Mod;
    return *this;
  }

  template <class T>
  Z_over_nZ<Mod> operator/=(const T& y) {
    x *= modinv(y, Mod);
    x %= Mod;
    return *this;
  }

  Z_over_nZ<Mod> operator+=(const Z_over_nZ<Mod>& y) {
    return (*this) += y.x;
  }

  Z_over_nZ<Mod> operator-=(const Z_over_nZ<Mod>& y) {
    return (*this) -= y.x;
  }

  Z_over_nZ<Mod> operator*=(const Z_over_nZ<Mod>& y) {
    return (*this) *= y.x;
  }

  Z_over_nZ<Mod> operator/=(const Z_over_nZ<Mod>& y) {
    return (*this) /= y.x;
  }

  template <class T>
  Z_over_nZ<Mod> operator+(const T& y) const {
    return Z_over_nZ(*this) += y;
  }

  template <class T>
  Z_over_nZ<Mod> operator-(const T& y) const {
    return Z_over_nZ(*this) -= y;
  }

  template <class T>
  Z_over_nZ<Mod> operator*(const T& y) const {
    return Z_over_nZ(*this) *= y;
  }

  template <class T>
  Z_over_nZ<Mod> operator/(const T& y) const {
    return Z_over_nZ(*this) /= y;
  }

  Z_over_nZ<Mod> operator-() const {
    return Z_over_nZ(Mod - x);
  }

  template <class T>
  bool operator!=(const T& y) const {
    return !(*this == y);
  }

  template <class T>
  bool operator==(const T& y) const {
    return (x - y) % Mod == 0;
  }

  bool operator==(const Z_over_nZ<Mod>& y) const {
    return (x - y.x) % Mod == 0;
  }

  template <class T>
  Z_over_nZ<Mod> operator=(const T& y) {
    x = y;
    return *this;
  }

  Z_over_nZ<Mod> operator=(const Z_over_nZ& y) {
    x = y.x;
    return *this;
  }

};

template <sl Mod>
ostream& operator<<(ostream& os, const Z_over_nZ<Mod>& x) {
  os << x.x;
  return os;
}

template <class T>
ostream& operator<<(ostream& os, const Matrix<T>& mat) {
  os << "[";
  FOR0(i, mat.N) {
    os << "[";
    FOR0(j, mat.M) {
      os << mat.mat[i][j];
      if (j != mat.M - 1) {
        os << ", ";
      }
    }
    os << "]";
    if (i != mat.N - 1) {
      os << ", ";
    }
  }
  os << "]";
  return os;
}

template <class T>
T powmod(T x, ul y, ul z) {
  T cur = x;
  T res = 1;
  while (y != 0) {
    if ((y & 1) == 1) {
      res = (res * cur) % z;
    }
    cur = (cur * cur) % z;
    y >>= 1;
  }
  return res;
}

static sl N, M;

using Zmod1000000007 = Z_over_nZ<1000000007>;

void solve(void) {
  Matrix<Zmod1000000007> mat(4, 4);
  Matrix<Zmod1000000007> yvec(4, 1);
  mat[0][0] = 1;
  mat[0][1] = 1;
  mat[0][2] = 2;
  mat[1][0] = 1;
  mat[2][0] = 1;
  mat[2][2] = 1;
  mat[3][0] = 1;
  mat[3][1] = 1;
  mat[3][2] = 2;
  mat[3][3] = 1;
  yvec[0][0] = 1;
  yvec[1][0] = 1;
  yvec[2][0] = 1;
  yvec[3][0] = 2;
  auto mat2 = mat.power(N - 2).mult(yvec);
  cout << mat2[3][0] << endl;
}

int main(void) {
  cin >> N >> M;
  solve();
  return 0;
}