結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
コンテスト
ユーザー 0w1
提出日時 2018-09-03 04:02:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,620 bytes
コンパイル時間 2,096 ms
コンパイル使用メモリ 206,768 KB
最終ジャッジ日時 2025-01-06 12:41:41
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
vector<vector<T>> mat_mul(vector<vector<T>> a, vector<vector<T>> b) {
  vector<vector<T>> c(a.size(), vector<T>(b[0].size()));
  for (int i = 0; i < a.size(); ++i)
    for (int j = 0; j < b.size(); ++j)
      for (int k = 0; k < b[j].size(); ++k)
        c[i][k] = c[i][k] + a[i][j] * b[j][k];
  return c;
}

template<typename T>
vector<vector<T>> mat_inv(vector<vector<T>> a) {
  if (a.size() == 2) {
    T t = a[0][0] * a[1][1] - a[0][1] * a[1][0];
    return {{a[1][1] / t, -a[0][1] / t}, {-a[1][0] / t, a[0][0] / t}};
  }
  return assert(false), a;
}

template<typename T>
vector<vector<T>> mat_sub(vector<vector<T>> a, vector<vector<T>> b) {
  vector<vector<T>> c(a.size(), vector<T>(a[0].size()));
  for (int i = 0; i < a.size(); ++i)
    for (int j = 0; j < a[0].size(); ++j)
      c[i][j] = a[i][j] - b[i][j];
  return c;
}

template<typename T>
vector<vector<T>> mat_pow(vector<vector<T>> a, long long p) {
  vector<vector<T>> r(a.size(), vector<T>(a.size()));
  for (int i = 0; i < r.size(); ++i) r[i][i] = 1;
  for (; p; p >>= 1) {
    if (p & 1) r = mat_mul(r, a);
    a = mat_mul(a, a);
  }
  return r;
}

template <int mod>
struct ModInt {
  int val;
  ModInt(int v = 0) : val((v % mod + mod) % mod) {}
  ModInt(long long v) : val((v % mod + mod) % mod) {}
  ModInt &operator=(int v) { return val = (v % mod + mod) % mod, *this; }
  ModInt &operator=(const ModInt &oth) { return val = oth.val, *this; }
  ModInt operator+(const ModInt &oth) const {
    int u = (val + oth.val) % mod;
    return u < 0 ? u + mod : u;
  }
  ModInt operator-(const ModInt &oth) const {
    int u = (val - oth.val) % mod;
    return u < 0 ? u + mod : u;
  }
  ModInt operator*(const ModInt &oth) const {
    return 1LL * val * oth.val % mod;
  }
  ModInt operator/(const ModInt &oth) const {
    function<int(int, int, int, int)> modinv = [&](int a, int b, int x, int y) {
      if (b == 0) return x < 0 ? x + mod : x;
      return modinv(b, a - a / b * b, y, x - a / b * y);
    };
    return *this * modinv(oth.val, mod, 1, 0);
  }
  ModInt operator-() const { return mod - val; }
};

signed main() {
  const int MOD = int(1e9 + 7);

  long long N;
  cin >> N;
  int M;
  cin >> M;

  vector<vector<ModInt<MOD>>> I = {{1, 0}, {0, 1}};
  vector<vector<ModInt<MOD>>> T = {{1, 1}, {1, 0}};
  vector<vector<ModInt<MOD>>> TM = mat_pow(T, M);
  vector<vector<ModInt<MOD>>> TMN = mat_pow(TM, N);
  vector<vector<ModInt<MOD>>> A0 = {{1}, {0}};

  cout << mat_mul(mat_mul(TM, mat_mul(mat_sub(I, TMN), mat_inv(mat_sub(I, TM)))), A0)[1][0].val << endl;

  return 0;
}
0