結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー | 303Yuyu |
提出日時 | 2020-06-10 23:19:04 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,080 bytes |
コンパイル時間 | 1,090 ms |
コンパイル使用メモリ | 107,324 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 19:30:45 |
合計ジャッジ時間 | 1,742 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
ソースコード
#include <iostream> #include <iomanip> #include <vector> #include <set> #include <string> #include <queue> #include <algorithm> #include <map> #include <cmath> #include <numeric> #include <list> #include <stack> #include <cstdio> #include <cstdlib> #include <cstring> #include <tuple> #include <deque> #include <complex> using namespace std; /* typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vpii; */ typedef long long ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef pair<long long, long long> pll; typedef vector<pll> vpll; typedef long double ld; typedef vector<ld> vld; typedef vector<bool> vb; #define rep(i, n) for (ll i = 0; i < (n); i++) #define reps(i, n) for (ll i = 1; i <= (n); i++) #define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--) #define rreps(i, n) for (ll i = (n); i >= 1; i--) #define all(v) (v).begin(), (v).end() template <class T> void chmin(T& a, T b) { a = min(a, b);} template <class T> void chmax(T& a, T b) { a = max(a, b);} constexpr int INF = 1 << 30; constexpr ll INFL = 1LL << 60; //constexpr ll MOD = 1000000007; constexpr ld EPS = 1e-12; ld PI = acos(-1.0); ll MOD; struct mint { ll x; mint(ll x=0):x((x%MOD+MOD)%MOD){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) {if ((x+=a.x)>=MOD) x-=MOD; return *this;} mint& operator-=(const mint a) {if ((x+=MOD-a.x)>=MOD) x-=MOD; return *this;} mint& operator*=(const mint a) {(x*=a.x)%=MOD; return *this;} mint operator+(const mint a) const {mint res(*this); return res+=a;} mint operator-(const mint a) const {mint res(*this); return res-=a;} mint operator*(const mint a) const {mint res(*this); return res*=a;} mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // For prime mod. // Do not use if MOD is not prime number !! mint inv() const { return pow(MOD-2);} mint& operator/=(const mint a) { return (*this) *= a.inv();} mint operator/(const mint a) const {mint res(*this); return res/=a;} }; typedef vector<mint> vm; struct Matrix { int n; vector<vm> mat; Matrix(int n) : n(n), mat(vector<vm>(n, vm(n))) {} Matrix(vector<vll>& a) : n(a.size()), mat(vector<vm>(n, vm(n))) { rep(i, n) rep(j, n) mat[i][j] = a[i][j]; } Matrix matmul(const Matrix& a) const{ Matrix res(n); rep(i, n) rep(j, n) rep(k, n) res.mat[i][j] += mat[i][k] * a.mat[k][j]; return res; } Matrix pow(ll k) const{ Matrix res(n); if(!k) { rep(i, n) res.mat[i][i] = 1; return res; } res = pow(k >> 1); res = res.matmul(res); if(k & 1) res = matmul(res); return res; } }; void solve() { ll n; cin >> n >> MOD; vvll a(2, vll(2)); a[0][0] = a[0][1] = a[1][0] = 1; Matrix m(a); m = m.pow(n - 2); cout << m.mat[0][0].x << endl; return; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); solve(); }