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

提出ソース

結果

問題	No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー	shinmirito
提出日時	2023-10-29 19:49:37
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	6,798 bytes
コンパイル時間	2,991 ms
コンパイル使用メモリ	253,172 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-25 16:53:16
合計ジャッジ時間	3,785 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

#define VT(Type) vector<Type>

typedef long long LI; typedef VT(LI) VI; typedef VT(VI) VVI; typedef VT(VVI) V3I; typedef VT(V3I) V4I;
typedef long double LD; typedef VT(LD) VD; typedef VT(VD) VVD;
typedef VT(bool) VB; typedef VT(VB) VVB;
typedef VT(string) VS; typedef VT(VS) VVS;
typedef pair<LI, LI> PII; typedef VT(PII) VPII; typedef VT(VPII) VVPII;
typedef pair<LD, LD> PDD; typedef VT(PDD) VPDD; typedef VT(VPDD) VVPDD;
typedef pair<string, LI> PSI; typedef VT(PSI) VPSI;
typedef set<LI> SI; typedef set<PII> SPII; typedef multiset<LI> mSI; typedef VT(SI) VSI;
typedef map<LI, LI> MII; typedef map<PII, LI> MPIII; typedef multimap<LI, LI> mMII; typedef VT(MII) VMII;
typedef map<string, LI> MSI; typedef multimap<string, LI> mMSI; typedef VT(MSI) VMSI;
typedef queue<LI> QI; typedef queue<PII> QPII;
typedef priority_queue<PII, VPII, greater<PII> > PQPII; //優先順位付きqueue（昇順）

#define PQD(Type) priority_queue<Type>
#define PQU(Type) priority_queue<Type, VT(Type), greater<Type> >
#define PQ(Type) priority_queue<Type, VT(Type), function<bool(Type, Type)> >

#define REP(i, j, k)	for(LI i = j; i < (LI)k; i++)
#define RREP(i, k, j)	for(LI i = j - 1; i >= (LI)k; i--)
#define rep(i, j)		REP(i, 0, j)
#define rrep(i, j)		RREP(i, 0, j)
#define vrep(a, v)		for(auto& a: v)
#define vcrep(a, v)		for(const auto& a: v)

// 要素数 R の部分集合を bit全探索
#define brep(bit, N, R) for (LI bit = bits(R) - 1, x, y; bit < bits(N); x = bit & -bit, y = bit + x, bit = (((bit & ~y) / x) >> 1) | y)

#define all(v)			v.begin(), v.end()
#define vsort(v)		sort(all(v));
#define vsorto(v, o)	sort(all(v), o);
#define vsortr(v)		vsorto(v, greater<LI>())

#define scan(Type, a)			Type a; cin >> a;
#define scan2(Type, a, b)		scan(Type, a) scan(Type, b)
#define scan3(Type, a, b, c)	scan2(Type, a, b) scan(Type, c)
#define scan4(Type, a, b, c, d) scan3(Type, a, b, c) scan(Type, d)

#define iscan(a)			scan(LI, a)
#define iscan2(a, b)		scan2(LI, a, b)
#define iscan3(a, b, c)		scan3(LI, a, b, c)
#define iscan4(a, b, c, d)	scan4(LI, a, b, c, d)

#define iscand(a)			iscan(a) a--;
#define iscand2(a, b)		iscand(a) iscand(b)
#define iscand3(a, b, c)	iscand2(a, b) iscand(c)
#define iscand4(a, b, c, d) iscand3(a, b, c) iscand(d)

#define sscan(a)			scan(string, a);
#define sscan2(a, b)		scan(string, a, b);

#define vscan(Type, A, N)			VT(Type) A(N);						rep(mci, N) cin >> A[mci];
#define vscan2(Type, A, B, N)		VT(Type) A(N), B(N);				rep(mci, N) cin >> A[mci] >> B[mci];
#define vscan3(Type, A, B, C, N)	VT(Type) A(N), B(N), C(N);			rep(mci, N) cin >> A[mci] >> B[mci] >> C[mci];
#define vscan4(Type, A, B, C, D, N) VT(Type) A(N), B(N), C(N), D(N);	rep(mci, N) cin >> A[mci] >> B[mci] >> C[mci] >> D[mci];
#define vvscan(Type, A, H, W)		VT(VT(Type)) A(H, VT(Type)(W));		rep(mch, H) rep(mcw, W) cin >> A[mch][mcw];

#define viscan(A, N)			vscan(LI, A, N)
#define viscan2(A, B, N)		vscan2(LI, A, B, N)
#define viscan3(A, B, C, N)		vscan3(LI, A, B, C, N)
#define viscan4(A, B, C, D, N)	vscan4(LI, A, B, C, D, N)
#define vviscan(A, H, W)		vvscan(LI, A, H, W)

#define viscand(A, N)			viscan(A, N)			rep(mci, N) A[mci]--;
#define viscand2(A, B, N)		viscan2(A, B, N)		rep(mci, N) { A[mci]--; B[mci]--; }
#define viscand3(A, B, C, N)	viscan3(A, B, C, N)		rep(mci, N) { A[mci]--; B[mci]--; C[mci]--; }
#define viscand4(A, B, C, D, N)	viscan4(A, B, C, D, N)	rep(mci, N) { A[mci]--; B[mci]--; C[mci]--; D[mci]--; }
#define vviscand(A, H, W)		vviscan(A, H, W)		rep(mch, H) rep(mcw, W) A[mch][mcw]--;

#define vpiscan(A, N)			VPII A(N); rep(mci, N) cin >> A[mci].first >> A[mci].second;
#define vpiscand(A, N)			vpiscan(A, N); rep(mci, N) { A[mci].first--; A[mci].second--; }
#define vpdscan(A, N)			VPDD A(N); rep(mci, N) cin >> A[mci].first >> A[mci].second;

#define vsscan(S, N)			vscan(string, S, N);

#define giscand(G, N, E) VVI G(N); rep(mci, E) { iscand2(mca, mcb); G[mca].push_back(mcb); }
#define gsscand(G, N, E) VVI G(N); rep(mci, E) { iscand2(mca, mcb); G[mca].push_back(mcb); G[mcb].push_back(mca); }

#define bits(x) (1LL << x)
#define inf(x) (x != INF ? x : -1)

#define maxa(a, b)		a = max(a, b);
#define mina(a, b)		a = min(a, b);
#define mida(a, b, c)	a = min(max(a, b), c);

#define px front().first
#define py front().second

#define miman(v, a) (lower_bound(all(v), a) - v.begin())
#define ika(v, a) (upper_bound(all(v), a) - v.begin())
#define ijo(v, a) (v.end() - lower_bound(all(v), a))
#define yorio(v, a) (v.end() - upper_bound(all(v), a))

#define debug(x) cout << ">> " << #x << " = " << x << endl;
#define el					cout << endl;

#define shown(a)			cout << (a) << " ";
#define shown2(a, b)		cout << (a) << " " << (b) << " ";
#define shown3(a, b, c)		cout << (a) << " " << (b) << " " << (c) << " ";
#define shown4(a, b, c, d)	cout << (a) << " " << (b) << " " << (c) << " " << (d) << " ";

#define show(a)				cout << (a) << endl;
#define show2(a, b)			cout << (a) << " " << (b) << endl;
#define show3(a, b, c)		cout << (a) << " " << (b) << " " << (c) << endl;
#define show4(a, b, c, d)	cout << (a) << " " << (b) << " " << (c) << " " << (d) << endl;

#define showif(f, a, b)		if(f) cout << (a) << endl; else cout << (b) << endl;

#define dshow(x, n)			cout << fixed << setprecision(n) << (x) << endl;
#define bshow(a, n)			show(bitset<n>(a))
#define pshow(a)			show2((a).first, (a).second)
#define pshown(a)			shown2((a).first, (a).second)
#define pshow2(a, b)		pshown(a) pshow(b)
#define ishow(a)			show(inf(a))
#define yes(f)				show(f ? "Yes" : "No")

#define vshown(A)			vcrep(a, A) { shown(a) } el
#define vshow(A)			vcrep(a, A) { show(a) }
#define vvshow(A)			vcrep(a, A) { vshown(a) }

#define vbshown(A, n)		vcrep(a, A) { shown(bitset<n>(a)) } el
#define vbshow(A, n)		vcrep(a, A) { show(bitset<n>(a)) }
#define vvbshow(A, n)		vcrep(a, A) { vbshow(a, n) }

#define vpshow(A)			vcrep(a, A) { pshow(a) }

#define vishow(A)			vcrep(a, A) { shown(inf(a)) } el
#define vvishow(A)			vcrep(a, A) { vishow(a) }

const LI INF = (1LL << 60);
//const LI MOD = 998244353;
const LI MOD = 1000000007;
const LD PI = acos(-1);

class MAT {
private:
	LI mod;
public:
	MAT(LI mod_) : mod(mod_) {}
	void tr(LI& n) {
		n = (n + mod) % mod;
	}
	VVI x(const VVI& A, const VVI& B) {
		VVI res(A.size(), VI(A.size(), 0));
		rep(i, A.size()) rep(j, B[0].size()) rep(k, A[i].size()) {
			res[i][j] += A[i][k] * B[k][j];
			tr(res[i][j]);
		}
		return res;
	}
	VVI matpow(VVI A, LI N) {
		VVI res(A.size(), VI(A.size(), 0));
		rep(i, A.size()) res[i][i] = 1;
		while (N) {
			if (N & 1) res = x(res, A);
			A = x(A, A);
			N >>= 1;
		}
		return res;
	}
};

int seisen_109() {
	iscan2(N, M);
	VVI A = { { 1, 1 }, { 1, 0 } };
	MAT mat(M);
	auto B = mat.matpow(A, N - 1);
	show(B[1][0]);
	return 0;
}

int main() {
	seisen_109();
	return 0;
}

yukicoder

結果

テストケース

ソースコード