結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2022-09-28 22:55:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,024 bytes |
コンパイル時間 | 2,419 ms |
コンパイル使用メモリ | 205,452 KB |
最終ジャッジ日時 | 2025-02-07 18:06:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i32 = int; using i64 = long long; vector<vector<i64>> mul(vector<vector<i64>>& as, vector<vector<i64>>& bs, i32 m) { assert(as[0].size() == bs.size()); vector res(as.size(), vector(bs[0].size(), 0LL)); for (size_t i = 0 ; i < as.size() ; i++) { for (size_t j = 0 ; j < bs[0].size() ; j++) { for (size_t k = 0 ; k < as[0].size() ; k++) { res[i][j] = (res[i][j] + as[i][k] * bs[k][j]) % m; } } } return res; } int main() { i32 n; cin >> n; i32 m; cin >> m; n--; const i32 lg = 32; vector dob(lg, vector(2, vector(2, 0LL))); dob[0] = { { 1LL, 1LL }, { 1LL, 0LL } }; for (i32 i = 0 ; i + 1 < lg ; i++) { dob[i + 1] = mul(dob[i], dob[i], m); } vector<vector<i64>> ans = { { 1LL, 0LL }, { 0LL, 1LL } }; for (i32 i = 0 ; i < lg ; i++) { if (n & (1 << i)) { ans = mul(ans, dob[i], m); } } cout << ans[1][0] << endl; }