結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー |
![]() |
提出日時 | 2022-08-03 16:19:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 2,201 bytes |
コンパイル時間 | 4,630 ms |
コンパイル使用メモリ | 257,292 KB |
最終ジャッジ日時 | 2025-01-30 17:21:36 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
// #define _GLIBCXX_DEBUG #include <bits/stdc++.h> #include <atcoder/all> // g++ main.cpp -std=c++17 -I . using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;} template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;} template<class T> void my_printv(vector<T> v,bool endline = true){ if(!v.empty()){ for(size_t i{}; i<v.size()-1; i++) cerr<<v[i]<<' '; cerr<<v.back(); } if(endline) cerr<<endl; } using ll = long long; const int inf = INT_MAX / 2; const ll INF = 1LL << 60; const ll MOD = 1000000007; // const int MOD = 998244353; // cout << fixed << setprecision(15) << ans << endl; // using mint = modint1000000007; using mint = modint998244353; // using mint = modint; //////////////////////////////////////////////////////////////////////////////////////////// ll n,m; template<class T> struct Matrix { int sz; vector<vector<T>> x; Matrix(int n) : sz(n) { x.assign(sz, vector<T> (sz, (T)0)); } vector<T> &operator [] (int i) { return x[i]; } Matrix<T> operator*(const Matrix& other) const { Matrix C(sz); for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { for (int k = 0; k < sz; k++) { C.x[i][j] = (C.x[i][j] + x[i][k] * other.x[k][j])%m; } } } return C; } Matrix pow(long long n) { Matrix Res(sz); Matrix Pow = *this; for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) Res.x[i][j] = (i == j); } while (n > 0) { if (n & 1) Res = Res * Pow; Pow = Pow * Pow; n >>= 1; } return Res; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Matrix<ll> mat(2); mat[0][0] = 1, mat[0][1] = 1, mat[1][0] = 1, mat[1][1] = 0; cin>>n>>m; auto ans = mat.pow(n-1)[1][0]; cout << ans << endl; // vector<ll> dp(2); // dp[0] = 0, dp[1] = 1; // rep(i, n-1) { // ll t = dp[1]; // dp[1] = (dp[0] + dp[1])%m; // dp[0] = t; // } // cout << dp[0] << endl; }