結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー hsyhsy
提出日時 2024-06-18 02:31:29
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,828 bytes
コンパイル時間 5,423 ms
コンパイル使用メモリ 275,072 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-18 02:31:36
合計ジャッジ時間 6,856 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<class T> using Tree=tree<T,null_type,std::less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
struct matrix{
	public:
	using value_type = T;
	private:
	std::vector<std::vector<value_type>> mat;
	int row, col;
	public:
	matrix() = default;
	matrix(int n) : matrix(n, n) {}
	matrix(int m, int n) : mat(m, std::vector<value_type>(n)), row(m), col(n) {}
	constexpr matrix operator+(const matrix rhs) const {
		return matrix(*this) += rhs;
	}
	constexpr matrix operator-(const matrix rhs) const {
		return matrix(*this) -= rhs;
	}
	constexpr matrix operator*(const matrix rhs) const {
		return matrix(*this) *= rhs;
	}
	constexpr matrix &operator+=(const matrix rhs) {
		static_assert(!mat.empty() && mat.row == rhs.row && mat.col == rhs.col);
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				mat[i][j] += rhs.mat[i][j];
			}
		}
	}
	constexpr matrix &operator-=(const matrix rhs) {
		static_assert(!mat.empty() && row == rhs.row && col == rhs.col);
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				mat[i][j] -= rhs.mat[i][j];
			}
		}
	}
	constexpr matrix operator*(const value_type a) const noexcept {
		return matrix(*this) *= a;
	}
	constexpr matrix operator*=(const value_type a) noexcept {
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				mat[i][j] *= a;
			}
		}
		return *this;
	}
	constexpr bool operator==(const matrix rhs) const noexcept {
		if (row != rhs.row || col != rhs.col) return false;
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				if (mat[i][j] != rhs.mat[i][j]) return false;
			}
		}
		return true;
	}
	constexpr bool operator!=(const matrix rhs) const noexcept {
		return !(matrix(*this) == rhs);
	}
	constexpr std::vector<value_type> &operator[](int pos) { return mat[pos]; }
	constexpr matrix mul(const matrix lhs, const matrix rhs) const {
		assert(lhs.col == rhs.row);
		matrix<value_type> res(lhs.row, rhs.col);
		for (int i = 0; i < lhs.row; ++i) {
			for (int k = 0; k < rhs.col; ++k) {
				for (int j = 0; j < lhs.col; ++j) {
					res.mat[i][j] += lhs.mat[i][k] * rhs.mat[k][j];
				}
			}
		}
		return res;
	}
	constexpr matrix pow(matrix x, long long n) {
		int len = x.row;
		matrix<value_type> res(len, len), a = x;
		for (int i = 0; i < len; ++i) {
			res[i][i] = 1;
		}
		while (n) {
			if (n & 1) res = mul(res, a);
			a = mul(a, a);
			n >>= 1;
		}
		return res;
	}
	constexpr int height() const { return row; }
	constexpr int width() const { return col; }
	friend std::ostream &operator<<(std::ostream &os, matrix &x) {
		for (int i = 0; i < x.row; ++i) {
			for (int j = 0; j < x.col; ++j) {
				os << x.mat[i][j] << (j + 1 == x.col ? "\n" : " ");
			}
		}
		return os;
	}
};

struct arbmodint{
	private:
	long long x;
	static long long &mod() {
		static long long mod_ = 0;
		return mod_;
	}
	public:
	arbmodint(const long long v = 0) {
		x = v;
		if (x >= get_mod()) x += get_mod();
		if (x < 0) x = x % get_mod() + get_mod();
	}
	static void set_mod(const long long m) { mod() = m; }
	static long long get_mod() { return mod(); }
	long long &val() noexcept { return x; }
	friend std::ostream &operator<<(std::ostream& os, arbmodint& b) {
		return os << b.x;
	}
	friend std::istream &operator>>(std::istream& is, arbmodint& b) {
		return is >> b.x;
	}
	arbmodint operator+(const arbmodint rhs) const {
		return arbmodint(*this) += rhs;
	}
	arbmodint operator-(const arbmodint rhs) const {
		return arbmodint(*this) -= rhs;
	}
	arbmodint operator*(const arbmodint rhs) const {
		return arbmodint(*this) *= rhs;
	}
	arbmodint operator/(const arbmodint rhs) const {
		return arbmodint(*this) /= rhs;
	}
	arbmodint &operator+=(const arbmodint rhs) {
		x += rhs.x;
		if(x >= get_mod()) x -= get_mod();
		return *this;
	}
	arbmodint &operator-=(const arbmodint rhs) {
		if (x < rhs.x) x += get_mod();
		x -= rhs.x;
		return *this;
	}
	arbmodint &operator*=(const arbmodint rhs) {
		x = x * rhs.x % get_mod();
		return *this;
	}
	arbmodint &operator/=(const arbmodint rhs) {
		return *this = *this * rhs.inv();
	}
	arbmodint inv() const {
		long long a = x, b = get_mod(), u = 1, v = 0, t;
		while (b) {
			t = a / b;
			a -= t * b;
			u -= t * v;
			std::swap(a, b);
			std::swap(u, v);
		}
		u %= get_mod();
		if (u < 0) u += get_mod();
		return u;
	}
	arbmodint pow(long long n) const {
		arbmodint a = *this, res = 1;
		while (n) {
			if (n & 1) res *= a;
			a *= a;
			n >>= 1;
		} 
		return res;
	}
};
using mint=arbmodint;
int main() {
	long long n,m;
	std::cin >>n >>m;
	mint::set_mod(m);
	matrix<mint> f(2,2);
	f[0][0]=f[0][1]=f[1][0]=mint(1);
	f=f.pow(f,n-2);
	std::cout <<f[0][0] <<"\n";
}
0