結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
|
提出日時 | 2020-05-09 11:49:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,198 bytes |
コンパイル時間 | 1,954 ms |
コンパイル使用メモリ | 175,056 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 15:44:30 |
合計ジャッジ時間 | 2,481 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> #define INF 5000000000000000000 #define ll long long #define pll pair<ll, ll> using namespace std; vector<vector<ll>> modmatmul(vector<vector<ll>>& a, vector<vector<ll>>& b, ll mod) { vector<vector<ll>> res(a.size(), vector<ll>(b.at(0).size())); for (ll row = 0; row < a.size(); ++row) { for (ll colom = 0; colom < b.at(0).size(); ++colom) { ll sum = 0; for (ll i = 0; i < b.size(); ++i) { sum = (sum + a.at(row).at(i) * b.at(i).at(colom) % mod) % mod; } res.at(row).at(colom) = sum; } } return res; } vector<vector<ll>> modmatpow(vector<vector<ll>> a, ll power, ll mod) { vector<vector<ll>> res(a.size(), vector<ll>(a.size(), 0)); for (ll i = 0; i < a.size(); ++i) { res.at(i).at(i) = 1; } while (power) { if (power & 1) { res = modmatmul(a, res, mod); } a = modmatmul(a, a, mod); power = (power >> 1); } return res; } int main() { ll N, mod; cin >> N >> mod; vector<vector<ll>> matrix = {{0, 1}, {1, 1}}; vector<vector<ll>> F = {{0}, {1}}; matrix = modmatpow(matrix, N - 2, mod); vector<vector<ll>> ans = modmatmul(matrix, F, mod); cout << ans.at(1).at(0) << "\n"; }