結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー tomonacci
提出日時 2020-06-29 12:42:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,979 bytes
コンパイル時間 466 ms
コンパイル使用メモリ 53,376 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 10:16:15
合計ジャッジ時間 1,236 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define int long long
#define dotimes(i, n) for (int i = 0, i##max__ = (n); i < i##max__; i++)
#define whole(x, f, ...) ([&](decltype((x)) c) { return (f)(begin(c), end(c), ## __VA_ARGS__); })(x)

int rint() {
  int x;
  scanf("%lld", &x);
  return x;
}

void wint(int x) {
  printf("%lld\n", x);
}

template<typename T> int size(T const& c) { return static_cast<int>(c.size()); }
template<typename T> bool maxs(T& a, T const& b) { return a < b ? a = b, true : false; }
template<typename T> bool mins(T& a, T const& b) { return a > b ? a = b, true : false; }
inline int lg(int x) { return 63 - __builtin_clzll(static_cast<unsigned int>(x)); }

int modulus;

int egcd_rec(int a, int b, int& x, int &y) {
  int q = b / a, r = b % a;
  if (r == 0) {
    x = 1 - q;
    y = 1;
    return a;
  }
  int d = egcd_rec(r, a, x, y);
  int z = x;
  x = y - x * q;
  y = z;
  return d;
}

inline int egcd(int a, int b, int& x, int& y) {
  if (abs(a) > abs(b))
    swap(a, b);
  int d = egcd_rec(a, b, x, y);
  if (d < 0) {
    d = -d;
    x = -x;
    y = -y;
  }
  return d;
}

class modint {
  int x;
public:
  modint() : x(0) {}
  modint(int x) : x(((x % ::modulus) + ::modulus) % ::modulus) {}
  int value() const {
    return x;
  }
  modint inv() const {
    int a, b;
    egcd(x, ::modulus, a, b);
    return modint(a);
  }
#define modint_operator_impl(op, impl) \
  modint operator op(modint const &y) const { \
    return impl; \
  } \
  modint operator op(int const &y) const { \
    return *this op modint(y); \
  } \
  modint& operator op##=(modint const& y) { \
    *this = *this op y; \
    return *this; \
  }
#define modint_operator(op) modint_operator_impl(op, modint(x op y.value()))
  modint_operator(+)
  modint_operator(-)
  modint_operator(*)
  modint_operator_impl(/, *this * y.inv())
#undef modint_operator
#undef modint_operator_impl
};

template<typename T>
class matrix {
  int m, n;
  vector<T> a;
public:
  matrix(int m, int n) : m(m), n(n), a(m * n) {}
  matrix(int m, int n, initializer_list<T> il) : m(m), n(n), a(il) {
    a.resize(m * n);
  }
  T& operator()(int i, int j) {
    return a[n*i+j];
  }
  const T& operator()(int i, int j) const {
    return a[n*i+j];
  }
  matrix& operator+=(matrix const& that) {
    dotimes(i, m) dotimes(j, n)
      (*this)(i, j) += that(i, j);
    return *this;
  }
  matrix operator*(matrix const& that) const {
    matrix r(m, that.n);
    dotimes(i, m) dotimes(j, n) dotimes(k, that.n)
      r(i, k) += (*this)(i, j) * that(j, k);
    return r;
  }
};

signed main() {
  const int N = rint();
  const int M = rint();
  ::modulus = M;
  matrix<modint>
    r(2, 2, {modint(1), modint(0), modint(0), modint(1)}),
    a(2, 2, {modint(1), modint(1), modint(1), modint(0)});
  for (int k = N-2; k; k >>= 1) {
    if (k & 1)
      r = r * a;
    a = a * a;
  }
  wint((r * matrix<modint>(2, 1, {modint(1), modint(0)}))(0, 0).value());
  return 0;
}
0