結果
| 問題 | 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 |
| コンパイル時間 | 3,158 ms |
| コンパイル使用メモリ | 254,484 KB |
| 実行使用メモリ | 4,348 KB |
| 最終ジャッジ日時 | 2023-10-29 19:49:41 |
| 合計ジャッジ時間 | 4,420 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 2 ms
4,348 KB |
| testcase_03 | AC | 2 ms
4,348 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | AC | 2 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,348 KB |
| testcase_08 | AC | 2 ms
4,348 KB |
| testcase_09 | AC | 2 ms
4,348 KB |
| testcase_10 | AC | 2 ms
4,348 KB |
| testcase_11 | AC | 2 ms
4,348 KB |
| testcase_12 | AC | 2 ms
4,348 KB |
| testcase_13 | AC | 2 ms
4,348 KB |
| testcase_14 | AC | 2 ms
4,348 KB |
ソースコード
#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;
}