結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
|
提出日時 | 2023-07-18 20:51:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 927 bytes |
コンパイル時間 | 1,835 ms |
コンパイル使用メモリ | 177,016 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 20:08:43 |
合計ジャッジ時間 | 2,779 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<vector<long long>> f(vector<vector<long long>> A, vector<vector<long long>> B, long long mod){ vector<vector<long long>> C(2,vector<long long>(2)); for(int i=0; i<2; i++){ for(int j=0; j<2; j++){ for(int k=0; k<2; k++){ C.at(i).at(j) += A.at(i).at(k) * B.at(k).at(j); C.at(i).at(j) %= mod; } } } return C; } vector<vector<long long>> modpow(vector<vector<long long>> A, long long n, long long mod){ vector<vector<long long>> ret={{1,0},{0,1}}; while(n > 0){ if(n & 1) ret = f(ret,A,mod); A = f(A,A,mod); n >>= 1; } return ret; } int main(){ long long N,M; cin >> N >> M; vector<vector<long long>> A = {{1,1},{1,2}}; vector<vector<long long>> ans = modpow(A,(N-1)/2,M); cout << ans.at((N+1)%2).at(1) << endl; return 0; }