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

提出ソース

結果

問題	No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー	morimario
提出日時	2020-04-15 12:44:25
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	5,481 bytes
コンパイル時間	2,010 ms
コンパイル使用メモリ	177,900 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-10-01 18:43:23
合計ジャッジ時間	2,801 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

// #define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define rep0(N) for (int COUNTER = 0; COUNTER < (int)(N); COUNTER++)
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define rep1(i, N) for (int i = 0; i < (int)(N); i++)
#define rep2(i, START, GOAL) for (int i = (int)(START); i < (int)(GOAL); i++)
#define rep3(i, START, GOAL) for (int i = (int)(START); i > (int)(GOAL); i--)
#define all(CONTAINER) CONTAINER.begin(), CONTAINER.end()
#define rall(CONTAINER) CONTAINER.rbegin(), CONTAINER.rend()
#define from1(CONTAINER) CONTAINER.begin() + 1, CONTAINER.end()
#define rfrom1(CONTAINER) CONTAINER.rbegin(), CONTAINER.rend() - 1
#define pout(X) cout << X << " "
#define print(X) cout << X << "\n"
#define output(X) cout << X << "\n"
#define dbe(X) cerr << X << " "
#define dbel(X) cerr << X << "\n"
#define dberr(X) cerr << X << " "
#define dberrl(X) cerr << X << "\n"
#define db(X) cerr << #X << ":" << (X) << " "
#define dbl(X) cerr << #X << ":" << (X) << "\n"
#define db2(X, Y) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << " "
#define db2l(X, Y) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << "\n"
#define dbl2(X, Y) cerr << #X << ":" << (X) << "\n" << #Y << ":" << (Y) << "\n"
#define db3(X, Y, Z) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << " " << #Z << ":" << (Z) << " "
#define db3l(X, Y, Z) cerr << #X << ":" << (X) << ", " << #Y << ":" << (Y) << ", " << #Z << ":" << (Z) << "\n"
#define dbl3(X, Y, Z) cerr << #X << ":" << (X) << "\n" << #Y << ":" << (Y) << "\n" << #Z << ":" << (Z) << "\n"
#define dbp(PAIR) cerr << #PAIR << ":(" << PAIR.first << ", " << PAIR.second << ") "
#define dbpl(PAIR) cerr << #PAIR << ":(" << PAIR.first << ", " << PAIR.second << ")\n"
#define dbt3(TUPLE3) cerr << #TUPLE3 << ":(" << get<0>(TUPLE3) << ", " << get<1>(TUPLE3) << ", " << get<2>(TUPLE3) << ") "
#define dbt3l(TUPLE3) cerr << #TUPLE3 << ":(" << get<0>(TUPLE3) << ", " << get<1>(TUPLE3) << ", " << get<2>(TUPLE3) << ")\n"
#define dbt4(TUPLE4) cerr << #TUPLE4 << ":(" << get<0>(TUPLE4) << ", " << get<1>(TUPLE4) << ", " << get<2>(TUPLE4) << ", " << get<3>(TUPLE4) << ") "
#define dbt4l(TUPLE4) cerr << #TUPLE4 << ":(" << get<0>(TUPLE4) << ", " << get<1>(TUPLE4) << ", " << get<2>(TUPLE4) << ", " << get<3>(TUPLE4) << ")\n"
#define dbv(VEC) cerr << #VEC << ":{ "; for (auto ELEM : VEC) cerr << ELEM << ", "; cerr << "}\n"
#define dbvp(VP) cerr << #VP << ":{ "; for (auto PAIR : VP) cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; cerr << "}\n"
#define dbvv(VV) cerr << #VV << ":{\n"; for (auto VEC : VV) { cerr << "{ "; for (auto ELEM : VEC) cerr << ELEM << ", "; cerr << "},\n"; } cerr << "}\n"
#define dbvvp(VVP) cerr << #VVP <<":{\n"; for (auto VP : VVP) { cerr << "{ "; for (auto PAIR : VP) { cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; } cerr << "},\n"; } cerr << "}\n";
#define dbs(SET) cerr << #SET << "{ "; for (auto ELEM : SET) cerr << ELEM << ", "; cerr << "}\n";
#define dbsp(SP) cerr << #SP << "{ "; for (auto PAIR : SP) cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; "}\n";
#define dbm(MAP) cerr << #MAP << ":{ "; for (auto PAIR : MAP) cerr << "(" << PAIR.first << ", " << PAIR.second << "), "; cerr << "}\n"
#define YN(f) cout << (f ? "YES" : "NO") << "\n"
#define Yn(f) cout << (f ? "Yes" : "No") << "\n"
#define yn(f) cout << (f ? "yes" : "no") << "\n"
using ll = long long;
using pii = pair<int, int>;using pll = pair<ll, ll>;using pdd = pair<double, double>;
using ti3 = tuple<int, int, int>;using tl3 = tuple<ll, ll, ll>;using td3 = tuple<double, double, double>;
using ti4 = tuple<int, int, int, int>;using tl4 = tuple<ll, ll, ll, ll>;using td4 = tuple<double, double, double, double>;
using vi = vector<int>;using vl = vector<ll>;using vd = vector<double>;using vs = vector<string>;using vb = vector<bool>;
using vvi = vector<vi>;using vvl = vector<vl>;using vvd = vector<vd>;using vvb = vector<vb>;
using vpii = vector<pii>;using vpll = vector<pll>;using vpdd = vector<pdd>;
using mii = map<int, int>;using mll = map<ll, ll>;
using si = set<int>;using sl = set<ll>;using ss = set<string>;
using spii = set<pii>;using spll = set<pll>;using spdd = set<pdd>;
// db

ll MOD;
ll rem(ll x) {
	x %= MOD; if(x < 0) x += MOD;
	return x;
}
ll madd(ll x, ll y) {
	return (rem(x) + rem(y)) % MOD;
}
ll msub(ll x, ll y) {
	return madd(x, -y);
}
ll mmul(ll x, ll y) {
	return rem(x) * rem(y) % MOD;
}

vvl matmul(vvl P, vvl Q) { // modmul
	assert(P[0].size() == Q.size());
	int d1 = P.size(), d2 = P[0].size(), d3 = Q[0].size();
	vvl res(d1, vl(d3));
	rep(i, d1) rep(j, d3) {
		ll temp = 0;
		rep(k, d2) temp = madd(temp, mmul(P[i][k], Q[k][j]));
		// rep(k, d2) temp += P[i][k] * Q[k][j];
		res[i][j] = temp;
	}
	return res;
}

vvl matpow(vvl P, ll x) { // P^x
	assert(P.size() == P[0].size());
	assert(x >= 0);
	int d = P.size();
	vvl res(d, vl(d));	rep(i, d) res[i][i] = 1; // E	
	vvl mul = P;
	// dbvv(res); dbvv(mul);
	while (x > 0) {
		// dbl(x); dbvv(res); dbvv(mul);
		if (x & 1) res = matmul(res, mul);
		mul = matmul(mul, mul);
		x >>= 1;
	}
	return res;	
}

int main() { // Matrix Power
	ll N, M; cin >> N >> M;
	MOD = M;
	vvl v = { { 1, }, { 0, }, }; // (F1,F0)^t
	vvl A = { // (F(n+2),F(n+1))=A(F(n+1),Fn)
		{ 1, 1 },
		{ 1, 0 },
	};
	/*
	rep(i, N) {
		dbl(i);
		dbvv(matpow(A, i));
		dbvv(matmul(matpow(A, i), v));
	}
	*/
	/*
	vvl ans = matmul(matpow(A, N - 1), v);
	dbvv(ans);
	dbl(ans[1][0]);
	*/
	print(matmul(matpow(A, N - 1), v)[1][0]);
}

yukicoder

結果

テストケース

ソースコード