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

• 問題: No.526 フィボナッチ数列の第N項をMで割った余りを求める
• ユーザー: Slephy
• 提出日時: 2022-10-04 13:11:14
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 7,176 bytes
• コンパイル時間: 4,308 ms
• コンパイル使用メモリ: 262,200 KB
• 最終ジャッジ日時: 2025-02-07 21:19:52
• ジャッジサーバーID （参考情報）: judge2 / judge2

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

ソースコード

// https://yukicoder.me/problems/no/526
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
    // using mint = modint1000000007;
    // using mint = modint998244353;
    using mint = modint;
    // const int MOD = mint::mod();
#endif
#ifdef LOCAL_DEBUG
    #define cout cout<<' '
#endif
using ll = long long;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
// constexpr int MOD = (int)1e9 + 7;
// constexpr int MOD = (int)998244353;
constexpr int INF = (int)1e9 + 1001010;
constexpr ll llINF = (ll)4e18 + 11000010;
constexpr double PI = 3.14159265358979;
constexpr double EPS = 1e-10;
#define Isize(x) (int)(size(x))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end());
#define endn "\n"
#define SUM(v) accumulate(ALL(v), 0LL)
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

template <class T> inline vector<vector<T>> vector2(const size_t &i, const size_t &j, const T &init = T()) {
    return vector<vector<T>>(i, vector<T>(j, init));
}
template <class T> inline vector<vector<vector<T>>> vector3(const size_t &i, const size_t &j, const int &k, const T &init = T()) {
    return vector<vector<vector<T>>>(i, vector<vector<T>>(j, vector<T>(k, init)));
}
template <class T> inline vector<vector<vector<vector<T>>>> vector4(const size_t &i, const size_t &j, const size_t &k, const size_t &l, const T &init = T()) {
    return vector<vector<vector<vector<T>>>>(i, vector<vector<vector<T>>>(j, vector<vector<T>>(k, vector<T>(l, init))));
}

const string VEC_ELEM_SEPARATION = " ";
const string VEC_VEC_SEPARATION = endn;
template<class T> istream & operator >> (istream &i, vector<T> &A) {for(auto &I : A) {i >> I;} return i;}
template<class T> ostream & operator << (ostream &o, const vector<vector<T>> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_VEC_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const vector<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const deque<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T, class U> istream & operator >> (istream &i, pair<T,U> &A) {i >> A.first >> A.second; return i;}
template<class T, class U> ostream & operator << (ostream &o, const pair<T,U> &A) {o << A.first << " " << A.second; return o;}
template<class T, class U, class V> istream & operator >> (istream &i, tuple<T,U,V>&A) {i >> get<0>(A) >> get<1>(A) >> get<2>(A); return i;}
template<class T, class U, class V> ostream & operator << (ostream &o, const tuple<T,U,V> &A) {o << get<0>(A) << " " << get<1>(A) << " " << get<2>(A); return o;}

template<class T> vector<T>& operator ++(vector<T> &A) {for(auto &I : A) {I++;} return A;}
template<class T> vector<T>& operator ++(vector<T> &A, int n) {for(auto &I : A) {I++;} return A;}
template<class T> vector<T>& operator --(vector<T> &A) {for(auto &I : A) {I--;} return A;}
template<class T> vector<T>& operator --(vector<T> &A, int n) {for(auto &I : A) {I--;} return A;}

template<class T, class U> bool chmax(T &a, const U &b){return ((a < b) ? (a = b, true) : false);}
template<class T, class U> bool chmin(T &a, const U &b){return ((a > b) ? (a = b, true) : false);}

ll floor(ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) != (b>0))) ? a/b-1 : a/b);}
ll ceil (ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) == (b>0))) ? a/b+1 : a/b);}
ll gcd(ll a, ll b){return ((b==0) ? a : gcd(b, a%b));}
ll lcm(ll a, ll b){return a / gcd(a,b) * b;}
bool is_in(ll n, ll inf, ll sup){return(inf <= n && n <= sup);}
// ================================== ここまでテンプレ ==================================


template<class T>
class Matrix{

public:
    // コンストラクタ
    Matrix(int h_, int w_, T init = T()) : h(h_), w(w_), mat(vector<vector<T>>(h_, vector<T>(w_, init))) {}
    Matrix(const vector<vector<T>> mat_) : h(mat_.size()), w(mat[0].size()), mat(mat_) {}
    Matrix(const Matrix<T> &mat_) : h(mat_.h), w(mat_.w), mat(mat_.mat) {}

    // 添え字演算子のオーバーロード
    vector<T>& operator [](int index){
        assert(0 <= index && index < h);
        return mat[index];
    }
    const vector<T> operator [](int index)const{
        assert(0 <= index && index < h);
        return mat[index];
    }

    // イテレータ
    auto begin() {return mat.begin();}
    auto end()   {return mat.end();}

    // 入出力ストリーム
    friend istream & operator >> (istream &i, Matrix<T> &mat) {for(auto &I : mat) for(auto &J : I){i >> J;} return i;}
    friend ostream & operator << (ostream &o, const Matrix &A) {o << A.mat; return o;}

    // 単位行列
    static Matrix<T> identity(unsigned int n){
        Matrix<T> res(n, n, 0);
        for(int i=0; i<n; i++){
            res[i][i] = 1;
        }
        return res;
    }
    static Matrix<T> identity(const Matrix<T> &mat_like){
        assert(mat_like.h == mat_like.w);
        return Matrix<T>::identity(mat_like.h);
    }

    // 算術演算子のオーバーロード
    Matrix<T> operator +(const Matrix<T> &other) const {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                res[i][j] = mat[i][j] + other[i][j];
            }
        }
        return res;
    }

    Matrix<T> operator -(const Matrix<T> &other) const {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                res[i][j] = mat[i][j] - other[i][j];
            }
        }
        return res;
    }

    Matrix<T> operator *(const Matrix<T> &other) const {
        assert(w == other.h);
        Matrix<T> res(h, other.w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < other.w; ++j){
                for (int k = 0; k < w; ++k){
                    res[i][j] += mat[i][k] * other[k][j];
                }
            }
        }
        return res;
    }

    // 行列累乗
    Matrix<T> pow(unsigned long long n) const{
        assert(h == w);
        Matrix<T> res = Matrix<T>::identity(h);
        Matrix<T> tmp = *this;
        while(n > 0){
            if(n & 1) res = res * tmp;
            tmp = tmp * tmp;
            n >>= 1;
        }
        return res;
    }

// メンバ変数
private:
    vector<vector<T>> mat;
public:
    int h, w;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m; cin >> n >> m;
    n--;
    mint::set_mod(m);
    Matrix<mint> a({{0, 1}, {1, 1}});
    // Matrix<mint> b = Matrix<mint>(vector<vector<mint>>{{0}, {1}});
    Matrix<mint> b(vector<vector<mint>>{{0}, {1}});
    auto p = a.pow(n);
    b = p * b;
    
    mint ans = b[0][0];
    cout << ans.val() << endl;
    return 0;
}