結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー |
|
提出日時 | 2021-03-12 16:25:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,324 bytes |
コンパイル時間 | 1,990 ms |
コンパイル使用メモリ | 201,752 KB |
最終ジャッジ日時 | 2025-01-19 13:50:56 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; //int:2*10**9 typedef long double ld; typedef pair<ll,ll> P; #define REP(i,n) for(ll i = 0; i<(ll)(n); i++) #define FOR(i,a,b) for(ll i=(a);i<=(b);i++) #define FORD(i,a,b) for(ll i=(a);i>=(b);i--) #define pb push_back #define MOD 1000000007 //998244353 #define PI 3.141592653 #define INF 100000000000000 //14 //cin.tie(0);cout.tie(0);ios::sync_with_stdio(false); vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll m) { vector<vector<ll>> c(a.size(),vector<ll>(b[0].size(),0)); REP(i,a.size()) REP(k,b[0].size()) REP(j,b.size()) { c[i][k]=(c[i][k]+(a[i][j]*b[j][k])%m)%m; } return c; } vector<vector<ll>> mat_pow(vector<vector<ll>> x, ll n, ll m) { vector<vector<ll>> y(x.size(),vector<ll>(x.size(),0)); REP(i,x.size()) y[i][i]=1; while (n) { if (n&1) y=mat_mul(x,y,m); x = mat_mul(x,x,m); n>>=1; } return y; } int main(){ ll n, m; cin >> n >> m; vector<vector<ll>> fib = {{0,1}}; vector<vector<ll>> t = {{0,1},{1,1}}; vector<vector<ll>> y = mat_pow(t,n-1,m); // cout << "test" << endl; // cout << y[0][0] << " " << y[0][1] << endl; // cout << y[1][0] << " " << y[1][1] << endl; y = mat_mul(fib,y,m); cout << y[0][0] << endl; }