結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー LanatusLanatus
提出日時 2022-12-03 10:42:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,943 bytes
コンパイル時間 2,690 ms
コンパイル使用メモリ 205,144 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-18 18:55:20
合計ジャッジ時間 2,991 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define all(v) begin(v), end(v)
#define endl '\n'

using namespace std;

#define int long long

using ull = unsigned long long;
using ll  = long long;
using ld  = long double;

const int MOD = 1e9 + 7;
const int MAX = 2000005;

#pragma region Macros

template <class S, class T> inline bool chmax(S &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class S, class T> inline bool chmin(S &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class S> using pq  = priority_queue<S>;
template <class S> using pqg = priority_queue<S, vector<S>, greater<S>>;


struct mint {
  ull a;

  constexpr mint(const ull x = 0) noexcept : a(x % MOD) {}
  constexpr mint operator + (const mint rhs) const noexcept { return mint(*this) += rhs; }
  constexpr mint operator - (const mint rhs) const noexcept { return mint(*this) -= rhs; }
  constexpr mint operator * (const mint rhs) const noexcept { return mint(*this) *= rhs; }
  constexpr mint operator / (const mint rhs) const noexcept { return mint(*this) /= rhs; }
  constexpr mint &operator += (const mint rhs) noexcept {
    a += rhs.a;
    if (a >= MOD) a -= MOD;
    return *this;
  }
  constexpr mint &operator -= (const mint rhs) noexcept {
    if (a < rhs.a) a += MOD;
    a -= rhs.a;
    return *this;
  }
  constexpr mint &operator *= (const mint rhs) noexcept {
    a = a * rhs.a % MOD;
    return *this;
  }
  constexpr mint &operator /= (mint rhs) noexcept {
    ull exp = MOD - 2;
    while (exp) {
      if (exp % 2) *this *= rhs;
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr mint pow(const mint &a, ull n) noexcept {
    if (n <= 0) return 1;
    auto t = pow(a, n / 2);
    t = t * t;
    if (n & 1) t = t * a;
    return t;
  }
};


long long modpow(long long a, long long n, long long m = MOD) {
  if (n <= 0) return 1LL;
  if (n % 2LL) return a * modpow(a, n-1) % MOD;
  long long t = modpow(a, n/2);
  return t % MOD * t % MOD;
}


struct Combination {
  const int MAX = 2e5 + 5;
  vector<long long> fact, invfact;

  Combination() {
    fact.resize(MAX);
    invfact.resize(MAX);

    fact[0] = 1;

    for (int i = 1; i < MAX; ++i) {
      fact[i] = fact[i-1] * i % MOD;
    }

    invfact[MAX-1] = modpow(fact[MAX-1], MOD-2);

    for (int i = MAX-1; i > 0; --i) {
      invfact[i-1] = invfact[i] * i % MOD;
    }
  }

  long long nCr(int n, int r) {
    long long a = fact[n];
    long long b = invfact[r] * invfact[n-r] % MOD;

    return a * b % MOD;
  }
};


struct Node {
  int from, to;
  ll d;

  Node(int from, int to, ll d): from(from), to(to), d(d) {}
  Node(int to, ll d): from(-1), to(to), d(d) {}
  Node() {}
};

using Graph = vector<vector<Node>>;

struct LCA {
  int n, k;
  vector<vector<int>> parent;
  vector<int> depth;
  vector<ll> dis;
 
 
  LCA(const Graph& G, int root = 0) : n(G.size()) {
    k = 1;
    while ((1LL << k) < n) ++k;
 
    parent.assign(k, vector<int>(n, -1));
    depth.assign(n, -1);
    dis.assign(n, 0);
 
    dfs(G, root, -1, 0);
 
    for (int i = 0; i < k-1; ++i) {
      for (int j = 0; j < n; ++j) {
        if (parent[i][j] == -1) parent[i+1][j] = -1;
        else parent[i+1][j] = parent[i][parent[i][j]];
      }
    }
  }
 
  void dfs(const Graph& G, int v, int p, int d) {
    depth[v] = d;
    parent[0][v] = p;
 
    for (auto e : G[v]) {
      if (e.to == p) continue;
      dis[e.to] = dis[v] ^ e.d;
      dfs(G, e.to, v, d + 1);
    }
  }
 
  int query(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    int diff = depth[x] - depth[y];
 
    for (int i = 0; diff > 0; diff /= 2, ++i) {
      if (diff & 1) {
        x = parent[i][x];
      }
    }
 
    if (x == y) return x;
 
    for (int i = k-1; i >= 0; --i) {
      if (parent[i][x] != parent[i][y]) {
        x = parent[i][x];
        y = parent[i][y];
      }
    }
 
    return parent[0][x];
  }
 
  ll get_dis(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[query(x, y)];
  }
  
  bool is_on_path(int x, int y, int a) {
    return get_dis(x, a) + get_dis(a, y) == get_dis(x, y);
  }
};

// 0-idx
struct RmaxQ {
  const ll INFLL = 1e18;
  int m;
  vector<long long> dat;
 
  RmaxQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, -INFLL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] = x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return -INFLL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return max(vl, vr);
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct RsumQ {
  const ll NIL = 0;
  int m;
  vector<long long> dat;
 
  RsumQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, NIL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] += x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = dat[i * 2 + 1] + dat[i * 2 + 2];
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return NIL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return vl + vr;
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct RminQ {
  const ll INFLL = 1e18;
  int m;
  vector<long long> dat;
 
  RminQ(int n) {
    m = 1;
    while (m < n) m *= 2;
 
    dat.assign(2 * m - 1, INFLL);
  }
 
  void update(int i, long long x) {
    i += m - 1;
    dat[i] = x;
 
    while (i) {
      i = (i - 1) / 2;
      dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
 
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (l >= b || r <= a) return INFLL;
    if (a <= l && r <= b) return dat[k];
    
    long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
 
    return min(vl, vr);
  }
 
  long long query_sub(int a, int b) {
    return query(a, b, 0, 0, m);
  }
};

struct UnionFind {
  int n;
  vector<int> parent, siz;
 
  UnionFind(int n) : n(n) {
    parent.resize(n);
    siz.resize(n);
 
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
      siz[i] = 1;
    }
  }
 
  int root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = root(parent[x]);
  }
 
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
 
    if (x == y) return false;
 
    if (siz[x] < siz[y]) swap(x, y);
    parent[y] = x;
    siz[x] += siz[y];
 
    return true;
  }
 
  int same(int x, int y) {
    return root(x) == root(y);
  }
 
  int size(int x) {
    return siz[root(x)];
  }
};

#pragma endregion

int mod;

vector<vector<int>> matrixMultiply(vector<vector<int>> a, vector<vector<int>> b) {
  int n = a.size(), m = b[0].size();
  int l = b.size();

  vector<vector<int>> ret(n, vector<int>(m, 0));
  if (b.size() != a[0].size()) return ret;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int k = 0; k < l; ++k) {
        ret[i][j] += a[i][k] % mod * b[k][j] % mod;
        ret[i][j] %= mod;
      }
    }
  }

  return ret;
}

vector<vector<int>> matrixPow(vector<vector<int>> &m, int n) {
  if (n == 0) return {{1, 0}, {0, 1}};
  if (n % 2) return matrixMultiply(m, matrixPow(m, n - 1));
  vector<vector<int>> mat = matrixPow(m, n / 2);
  return matrixMultiply(mat, mat);
}

signed main(void) {
  vector<vector<int>> mat {
    {0, 1},
    {1, 1}
  };

  int n;
  cin >> n;

  // mod = MOD;
  cin >> mod;

  vector<vector<int>> p = matrixPow(mat, n - 1);
  vector<vector<int>> a {
    {0},
    {1}
  };

  vector<vector<int>> ans = matrixMultiply(p, a);
  cout << ans[0][0] << endl;
  return 0;
}
0