結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
コンテスト
ユーザー legosuke
提出日時 2019-06-10 14:58:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,045 bytes
コンパイル時間 2,299 ms
コンパイル使用メモリ 175,732 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 00:38:28
合計ジャッジ時間 2,494 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

template <typename T>
struct Matrix {
  vector<vector<T>> A;
  Matrix() {}
  Matrix(size_t n, size_t m) : A(n,vector<T>(m,0)) {}
  Matrix(size_t n) : A(n, vector<T>(n,0)) {}
  size_t height() const {
    return (A.size());
  }
  size_t width() const {
    return (A[0].size());
  }
  inline const vector<T> &operator[](int k) const {
    return (A.at(k));
  }
  inline vector<T> &operator[](int k) {
    return (A.at(k));
  }
  static Matrix I(size_t n) {
    Matrix mat(n);
    for (int i = 0; i < n; i++) mat[i][i] = 1;
    return (mat);
  }
  Matrix &operator+=(const Matrix &B) {
    size_t n = height(), m = width();
    assert(n == B.height() && m == B.width());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        ((*this)[i][j] += B[i][j]) %= MOD;
    return (*this);
  }
  Matrix &operator-=(const Matrix &B) {
    size_t n = height(), m = width();
    assert(n == B.height() && m == B.width());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        ((*this)[i][j] += MOD - B[i][j]) %= MOD;
    return (*this);
  }
  Matrix &operator*=(const Matrix &B) {
    size_t n = height(), m = B.width(), p = width();
    assert(p == B.height());
    vector<vector<T>> C(n,vector<T>(m,0));
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        for (int k = 0; k < p; k++)
          C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j] % MOD) % MOD;
    A.swap(C);
    return (*this);
  }
  Matrix &operator^=(int k) {
    Matrix B = Matrix::I(height());
    while (k > 0) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1;
    }
    A.swap(B.A);
    return (*this);
  }
  Matrix operator+(const Matrix &B) const {
    return (Matrix(*this) += B);
  }
  Matrix operator-(const Matrix &B) const {
    return (Matrix(*this) += MOD - B);
  }
  Matrix operator*(const Matrix &B) const {
    return (Matrix(*this) *= B);
  }
  Matrix operator^(const int k) const {
    return (Matrix(*this) ^= k);
  }
  friend ostream &operator<<(ostream &os, Matrix &p) {
    size_t n = p.height(), m = p.width();
    for (int i = 0; i < n; i++) {
      os << "[";
      for (int j = 0; j < m; j++) {
        os << p[i][j] << (j + 1 == m ? "]\n" : ".");
      }
    }
    return (os);
  }
};

int pow_mod(int a, int n, int m = MOD) {
  int res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return res;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int N,M;
  cin >> N >> M;
  Matrix<int> A(2,2);
  A[0][0] = 1; A[0][1] = 1; A[1][0] = 1;
  Matrix<int> X(2,1);
  X[0][0] = 1;
  X = (A ^ (M-1)) * X;
  int f = X[0][0];
  X[0][0] = 3; X[1][0] = 1;
  X = (A ^ (M-2)) * X;
  int g = X[0][0];
  X[0][0] = 1; X[1][0] = 1;
  X = (A ^ (M-2)) * X;
  int h = X[0][0];
  Matrix<int> P(3,3),Q(3,1);
  P[0][0] = g; P[0][1] = ((M-1)&1 ? pow_mod(MOD-1,MOD-2) : 1); P[0][2] = h;
  P[1][0] = 1; P[2][2] = 1;
  Q[0][0] = f; Q[1][0] = 0; Q[2][0] = 1;
  Q = (P ^ (N-1)) * Q;
  cout << Q[0][0] << endl;

  return 0;
}
0