結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー SlephySlephy
提出日時 2022-10-03 17:16:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,129 bytes
コンパイル時間 4,483 ms
コンパイル使用メモリ 270,848 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-27 16:21:07
合計ジャッジ時間 5,295 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#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);

    int 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 = Matrix<mint>(2, 1, 1);
    auto p = a.pow(n);
    b = p * b;
    
    mint ans = b[0][0];
    cout << ans.val() << endl;
    return 0;
}
0