結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー | yumekawayui |
提出日時 | 2024-06-10 00:40:05 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,813 bytes |
コンパイル時間 | 4,139 ms |
コンパイル使用メモリ | 165,504 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-10 00:40:12 |
合計ジャッジ時間 | 4,775 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; const vector<int> dx = {0, 0, 1, -1}; const vector<int> dy = {1, -1, 0, 0}; #define vec vector #define int long long #define double long double #define ll long long #define pii pair<int,int> #define pq priority_queue #define all(V) begin(V),end(V) #define tple tuple<int,int,int> template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } #define nexper(Z) next_permutation(all(Z)) #define pb push_back #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define req(i, x, n) for (int i = x; i < (int)(n); i++) #define rex(i, n) for (int i = 1; i <= (int)(n); i++) #define rey(i, x, n) for (int i = x; i <= (int)(n); i++) #define cleout(i) cout << fixed << setprecision(i) vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) { // 行列乗算 int n = a.size(); vector<vector<ll>> res(n, vector<ll>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { res[i][j] += a[i][k] * b[k][j]; res[i][j] %= mod; } } } return res; } vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) { // 行列累乗 int n = a.size(); vector<vector<ll>> res(n, vector<ll>(n)); for (int i = 0; i < n; i++) res[i][i] = 1; while (b) { if (b & 1) res = mat_mul(res, a, mod); a = mat_mul(a, a, mod); b >>= 1; } return res; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m;cin>>n>>m; vec<vec<int>> mat={ {1,1},{1,0} }; if(n<=2){ cout<<1<<endl;return 0; } vec<vec<int>> Z=mat_pow(mat,n-1,m); cout<<Z[0][0]<<endl; return 0; }