結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー coindarw
提出日時 2021-01-01 22:32:01
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,943 bytes
コンパイル時間 3,489 ms
コンパイル使用メモリ 164,648 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 12:16:08
合計ジャッジ時間 4,382 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (ll i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (ll i = ((ll)(n)-1); i >= 0; --i)
#define rreps(i, n) for (ll i = ((ll)(n)); i > 0; --i)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define repc2(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
ll N, M;

typedef vector<vector<ll> > Matrix;
typedef vector<ll> vec;

Matrix new_matrix(int n) {
    Matrix res(n, vec(n));
    rep(i, n) { res[i][i] = 1; }
    return res;
}
Matrix new_matrix(int n, int m) {
    Matrix res(n, vec(m));
    return res;
}
Matrix operator*(const Matrix &m1, const Matrix &m2) {
    assert(m1.at(0).size() == m2.size());
    size_t n = m1.size();
    size_t m = m2.at(0).size();
    size_t l = m2.size();
    Matrix res(n, vec(m));
    rep(i, n) rep(j, m) rep(k, l) {
        res.at(i).at(j) += m1.at(i).at(k) * m2.at(k).at(j);
        res.at(i).at(j) %= M;
    }
    return res;
}
vec operator*(const Matrix &m, const vec &v) {
    assert(m.at(0).size() == v.size());
    vec res(v.size());
    rep(i, v.size()) rep(j, m.at(0).size()) {
        res.at(i) += m.at(i).at(j) * v.at(j);
        res.at(i) %= M;
    }
    return res;
}
Matrix E(size_t n) {
    Matrix res(n, vec(n));
    rep(i, n) res.at(i).at(i) = 1;
    return res;
}
Matrix pow(const Matrix &a, long long n) {
    Matrix b = a;
    Matrix res = E(a.size());
    while (n > 0) {
        if (n & 1)
            res = res * b;
        b = b * b;
        n >>= 1ll;
    }
    return res;
}

int main() {
    cin >> N >> M;
    Matrix mat = new_matrix(2);
    vec v = vector<ll>(2, 1);
    mat.at(0).at(0) = mat.at(0).at(1) = mat.at(1).at(0) = 1;
    mat.at(1).at(1) = 0;
    cout << pow(mat, N - 1).at(0).at(1) << endl;
    return 0;
}
0