結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2021-06-19 01:53:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,545 bytes |
コンパイル時間 | 2,576 ms |
コンパイル使用メモリ | 217,580 KB |
最終ジャッジ日時 | 2025-01-22 09:55:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#pragma region Macros // #pragma GCC target("avx2") #pragma GCC optimize("O3") #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define rrep(i, n) for (int i = (n - 1); i >= 0; i--) #define ALL(v) v.begin(), v.end() #define endl "\n" #define popcount(bit) __builtin_popcount(bit) #define pb push_back #define eb emplace_back using namespace std; using P = pair<int, int>; typedef long long ll; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int fx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const int fy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; using Mat = vector<vector<ll>>; ll mod; Mat mul(Mat &a, Mat &b){ int n = a.size(); int l = b.size(); int m = b[0].size(); Mat ans(n, vector<ll>(m, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < l; j++) for (int k = 0; k < m; k++) ans[i][k] = (ans[i][k] + a[i][j] * b[j][k]) % mod; return ans; } Mat matpow(Mat A, ll n){ Mat B = Mat(A.size(), vector<ll>(A.size())); rep(i, A.size()) B[i][i] = 1; while(n > 0){ if(n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } //verify https://yukicoder.me/problems/no/526 int main() { ll n, m; cin >> n >> m; mod = m; Mat A(2, vector<ll>(2)); A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A[1][1] = 0; A = matpow(A, n-1); cout << A[1][0] << endl; }