#1169737 (C++23) No.526 フィボナッチ数列の第N項をMで割った余りを求める

• 問題: No.526 フィボナッチ数列の第N項をMで割った余りを求める
• ユーザー: めーらく
• 提出日時: 2026-06-27 17:45:46
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,361 bytes
• コンパイル時間: 4,188 ms
• コンパイル使用メモリ: 340,540 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-06-27 17:45:57
• 合計ジャッジ時間: 10,602 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 12

ソースコード

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using vb = vector<bool>;
using vi = vector<int>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vs = vector<string>;
using vc = vector<char>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define rrep(i,n) for(int i = (int)(n) - 1; i>=0; i--)
#define rep1(i,n) for(int i=1; i <=(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n); i++)
template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool chmin(T& a, const T& b){if(b<a){a=b;return true;}return false;}
template<class T> bool chmax(T& a, const T& b){if(a<b){a=b;return true;}return false;}

const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};

const int INF = 1e9;
const ll LINF = 1e18;

struct Matrix {
    using ll = long long;
    int n, m;
    ll mod;
    vector<vector<ll>> a;

    Matrix(int n, int m, ll mod) : n(n), m(m), mod(mod), a(n, vector<ll>(m, 0)) {}
    Matrix(const vector<vector<ll>>& v, ll mod)
        : n(v.size()), m(v.empty() ? 0 : v[0].size()), mod(mod), a(v) {
        normalize();
    }

    void normalize() {
        for (auto& row : a)
            for (auto& x : row) x = ((x % mod) + mod) % mod;
    }

    static Matrix identity(int n, ll mod) {
        Matrix I(n, n, mod);
        for (int i = 0; i < n; i++) I.a[i][i] = 1 % mod;
        return I;
    }

    vector<ll>& operator[](int i) { return a[i]; }
    const vector<ll>& operator[](int i) const { return a[i]; }

    Matrix operator*(const Matrix& B) const {
        assert(m == B.n && mod == B.mod);
        Matrix C(n, B.m, mod);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < m; k++) {
                ll x = a[i][k];
                if (!x) continue;
                for (int j = 0; j < B.m; j++) {
                    C.a[i][j] = (C.a[i][j] + (__int128)x * B.a[k][j]) % mod;
                }
            }
        }
        return C;
    }

    vector<ll> operator*(const vector<ll>& v) const {
        assert((int)v.size() == m);
        vector<ll> r(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!a[i][j]) continue;
                r[i] = (r[i] + (__int128)a[i][j] * v[j]) % mod;
            }
        }
        return r;
    }

    Matrix pow(ll p) const {
        assert(n == m);
        Matrix R = identity(n, mod), A = *this;
        while (p > 0) {
            if (p & 1) R = R * A;
            A = A * A;
            p >>= 1;
        }
        return R;
    }

    Matrix operator+(const Matrix& B) const {
        assert(n == B.n && m == B.m && mod == B.mod);
        Matrix C(n, m, mod);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                C.a[i][j] = (a[i][j] + B.a[i][j]) % mod;
        return C;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(16);

    ll n,m;
    cin >> n >> m;
    Matrix a(2,2,m);
    a[0][0]=1;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=0;
    Matrix want = a.pow(n);
    vll times={0,1};
    vll ans=want*times;
    cout << ans[1] << endl;


    
    
}