結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー まみめ
提出日時 2025-05-14 19:13:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,811 bytes
コンパイル時間 4,522 ms
コンパイル使用メモリ 282,148 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 19:13:48
合計ジャッジ時間 4,316 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <class T> struct Matrix {
    vector<vector<T>> A;

    Matrix() {}

    Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}

    Matrix(size_t n) : A(n, vector<T>(n, 0)) {};

    size_t height() const { return (A.size()); }

    size_t width() const { return (A[0].size()); }

    inline const vector<T> &operator[](int k) const { return (A.at(k)); }

    inline vector<T> &operator[](int k) { return (A.at(k)); }

    static Matrix I(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++)
            mat[i][i] = 1;
        return (mat);
    }

    Matrix &operator+=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector<vector<T>> C(n, vector<T>(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix pow(long long k) {
        Matrix B = Matrix::I(height());
        while (k > 0) {
            if (k & 1)
                B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }

    Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }

    Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }

    friend ostream &operator<<(ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }

    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0)
                    idx = j;
            }
            if (idx == -1)
                return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

// 任意の mod をとれる modint
// mint::set_mod(M); で設定
class rmint {
    long long x;
    static long long mod; // mod は static メンバで共有

  public:
    rmint(long long x_ = 0) { x = (x_ % mod + mod) % mod; }

    static void set_mod(long long m) { mod = m; }

    rmint &operator+=(const rmint &a) {
        x += a.x;
        if (x >= mod)
            x -= mod;
        return *this;
    }

    rmint &operator-=(const rmint &a) {
        x += mod - a.x;
        if (x >= mod)
            x -= mod;
        return *this;
    }

    rmint &operator*=(const rmint &a) {
        x = x * a.x % mod;
        return *this;
    }

    rmint operator+(const rmint &a) const { return rmint(*this) += a; }
    rmint operator-(const rmint &a) const { return rmint(*this) -= a; }
    rmint operator*(const rmint &a) const { return rmint(*this) *= a; }

    rmint pow(long long r) const {
        rmint res(1), base(*this);
        while (r > 0) {
            if (r & 1)
                res *= base;
            base *= base;
            r >>= 1;
        }
        return res;
    }

    friend std::ostream &operator<<(std::ostream &os, const rmint &m) {
        return os << m.x;
    }

    long long val() const { return x; }
};

long long rmint::mod = 1;

long long N, M;

int main() {
    cin >> N >> M;
    N--;
    rmint::set_mod(M);
    Matrix<rmint> A(2, 1), X(2, 2);
    X[0][0] = 1, X[0][1] = 1, X[1][0] = 1;
    A[0][0] = 1, A[0][1] = 0;
    auto ans = X.pow(N);
    cout << ans[1][0] << endl;
    return 0;
}
0