結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
|
提出日時 | 2023-01-20 19:15:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 857 bytes |
コンパイル時間 | 2,025 ms |
コンパイル使用メモリ | 197,416 KB |
最終ジャッジ日時 | 2025-02-10 04:17:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using tll = tuple<ll, ll, ll>; using mat = tuple<ll, ll, ll, ll>; ll N, M; vector<mat> ma; mat calc_mat(mat a, mat b) { mat n; auto& [n00, n01, n10, n11] = n; auto [a00, a01, a10, a11] = a; auto [b00, b01, b10, b11] = b; n00 = ((a00 * b00) % M + (a01 * b10) % M) % M; n01 = ((a00 * b10) % M + (a01 * b11) % M) % M; n10 = ((a10 * b00) % M + (a11 * b10) % M) % M; n11 = ((a10 * b10) % M + (a11 * b11) % M) % M; return n; } mat pow_mat(mat a, ll n, ll m) { mat ret = {1, 0, 0, 1}; while (n) { if (n & 1) ret = calc_mat(ret, a); a = calc_mat(a, a); n >>= 1; } return ret; } int main() { cin >> N >> M; mat ans = pow_mat(mat(1, 1, 1, 0), N - 1, M); cout << get<2>(ans) << endl; return 0; }