結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー AC2K
提出日時 2023-03-12 18:48:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 6,155 bytes
コンパイル時間 1,916 ms
コンパイル使用メモリ 203,684 KB
最終ジャッジ日時 2025-02-11 10:42:07
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "library/template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
#define all(x) (x).begin(),(x).end()
#define popcount(x) __builtin_popcount(x)
using i128=__int128_t;
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
using P = pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = { 1,0,-1,0 };
constexpr int dy[] = { 0,1,0,-1 };
template<class T>inline void chmax(T&x,T y){if(x<y)x=y;}
template<class T>inline void chmin(T&x,T y){if(x>y)x=y;}
#line 2 "library/math/matrix.hpp"
template<typename T>
class Matrix {
    vector<vector<T>> dat;
    int h = 0, w = 0;

  public:
    Matrix(const vector<vector<T>>& dat)
        : dat(dat), h(dat.size()), w(dat.front().size()) {}

    Matrix(int h_, int w_, const T& v = T())
        : dat(h_, vector<T>(w_, v)){}
        
    using mat = Matrix<T>;
    //access
    vector<T>& operator[](int i) { return dat[i]; }

    //operator
    mat& operator+=(const mat& r) {
        assert(r.h == this->h);
        assert(r.w == this->w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dat[i][j] += r.dat[i][j];
            }
        }
        return (*this);
    }
    mat& operator-=(const mat&r){
        assert(r.h == this->h);
        assert(r.w == this->w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dat[i][j] -= r.dat[i][j];
            }
        }
        return (*this);
    }
    mat& operator*=(const mat& r) {
        int ha = dat.size(), wa = dat.front().size();
        int hb = r.dat.size(), wb = r.dat.front().size();
        assert(wa == hb);

        vector<vector<T>> res(ha, vector<T>(wb));
        rep(i, ha) rep(j, wb) rep(k, wa) {
            res[i][j] += dat[i][k] * r.dat[k][j];
        }
        swap(res, dat);
        return (*this);
    }

    mat operator+(const mat& r) { return mat(*this) += r; }
    mat operator-(const mat& r) { return mat(*this) -= r; }
    mat operator*(const mat& r) { return mat(*this) *= r; }

    mat pow(__uint64_t e) const {
        mat pr(h, h);
        rep(i, h) { pr[i][i] = 1; }
        mat pw(*this);
        while(e){
            if(e&1){
                pr *= pw;
            }
            pw *= pw;
            e >>= 1;
        }
        return pr;
    }
};
#line 2 "library/math/barrett.hpp"
namespace internal {
	//barret reduction
	class barrett {
		using u32 = uint32_t;
		using u64 = uint64_t;

		u32 m;
		u64 im;
	public:
		explicit barrett() = default;
		explicit barrett(const u32& m_) :m(m_), im((u64)(-1) / m_ + 1) {}

		u32 get_mod() const { return m; }
		u32 mul(u32 a, u32 b) {
			if (a == 0 || b == 0) {
				return 0;
			}
			u64 z = a;
			z *= b;
#ifdef _MSC_VER
			u64 x;

			_umul128(z, im, &x);
#else
			u64 x = (u64)(((__uint128_t)(z)*im) >> 64);
#endif

			u32 v = (u32)(z - x * m);

			if (v >= m)v += m;
			return v;
		}
	};
}
#line 3 "library/math/dynamic_modint.hpp"
class dynamic_modint32 {
	using u32 = uint32_t;
	using u64 = uint64_t;

	using i32 = int32_t;
	using i64 = int64_t;
	using br = internal::barrett;

	static br brt;
	static u32 mod;
	u32 v;	//value
public:
	static void set_mod(const u32& mod_) {
		brt = br(mod_);
		mod = mod_;
	}
private:
	u32 normalize(const i64& x) const {
		i32 m = x % mod;
		if (m < 0) {
			m += mod;
		}
		return m;
	}
public:
	dynamic_modint32() :v(0) { assert(mod); }	//modが決定済みである必要がある
	dynamic_modint32(const i64& v_) :v(normalize(v_)) { assert(mod); }	

	u32 val() const { return v; }

	using mint = dynamic_modint32;

	//operators
	mint& operator=(const i64& r) {
		v = normalize(r); 
		return (*this);
	}
	mint& operator+=(const mint& r) {
		v += r.v;
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	mint& operator-=(const mint&r) {
		v += mod - r.v;
		if (v >= mod) {
			v -= mod;
		}

		return (*this);
	}
	mint& operator*=(const mint& r) {
		v = brt.mul(v, r.v);
		return (*this);
	}

	mint operator+(const mint& r) const { return mint(*this) += r; }
	mint operator-(const mint& r) const { return mint(*this) -= r; }
	mint operator*(const mint& r) const { return mint(*this) *= r; }



	mint& operator+= (const i64& r) { return (*this) += mint(r); }
	mint& operator-= (const i64& r) { return (*this) -= mint(r); }
	mint& operator*= (const i64& r) { return (*this) *= mint(r); }

	friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; }
	friend mint operator+(const mint& l, const i64& r) { return mint(l) += r; }
	friend mint operator-(const i64& l, const mint& r) { return mint(l) -= r; }
	friend mint operator-(const mint& l, const i64& r) { return mint(l) -= r; }
	friend mint operator*(const i64& l, const mint& r) { return mint(l) *= r; }
	friend mint operator*(const mint& l, const i64& r) { return mint(l) += r; }


	friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	friend istream& operator>>(istream& is, mint& mt) {
		i64 v_;
		is >> v_;
		mt = v_;
		return is;
	}
	mint pow(u64 e) const {
		mint res(1), base(*this);

		while (e) {
			if (e & 1) {
				res *= base;
			}
			e >>= 1;
			base *= base;
		}
		return base;
	}
	mint inv() const {
		return pow(mod - 2);
	}

	mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
	mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
	mint& operator/=(const i64& r) { return (*this) /= mint(r); }
	friend mint operator/(const mint& l, const i64& r) { return mint(l) /= r; }
	friend mint operator/(const i64& l, const mint& r) { return mint(l) /= r; }
};
typename dynamic_modint32::u32 dynamic_modint32::mod;
typename dynamic_modint32::br dynamic_modint32::brt;

///@brief dynamic modint(動的modint)
///@docs docs/math/dynamic_modint.md
#line 4 "main.cpp"

using mint = dynamic_modint32;
int main() {
    int n,m;
    cin >> n >> m;
    mint::set_mod(m);

    Matrix<mint> A({{1, 1}, {1, 0}});
    A = A.pow(n - 2);
    cout << A[0][0] << '\n';
}
0