結果
問題 |
No.3228 Very Large Fibonacci Sum
|
ユーザー |
![]() |
提出日時 | 2025-08-11 11:09:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 3,046 bytes |
コンパイル時間 | 450 ms |
コンパイル使用メモリ | 46,536 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-11 11:10:00 |
合計ジャッジ時間 | 1,695 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
コンパイルメッセージ
main.cpp: In function ‘void printmat(int, const mi (*)[4])’: main.cpp:116:16: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘const mi’ {aka ‘const MI<1000000007>’} [-Wformat=] 116 | printf("%d", a[i][j]); | ~^ ~~~~~~~ | | | | int const mi {aka const MI<1000000007>} main.cpp: In function ‘int main()’: main.cpp:127:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 127 | scanf("%d%d%d%d%d%lld", &a, &b, &c, &d, &e, &n); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3228.cc: No.3228 Very Large Fibonacci Sum - yukicoder */ #include<cstdio> #include<algorithm> using namespace std; /* constant */ const int M = 4; const int MOD = 1000000007; /* typedef */ using ll = long long; template<const int MOD> struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(int n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI<MOD>; using vec = mi[M]; using mat = vec[M]; /* global variables */ /* subroutines */ inline void initvec(const int n, vec a) { fill(a, a + n, 0); } inline void initmat(const int n, mat a) { for (int i = 0; i < n; i++) initvec(n, a[i]); } inline void unitmat(const int n, mat a) { initmat(n, a); for (int i = 0; i < n; i++) a[i][i] = 1; } inline void copymat(const int n, const mat a, mat b) { for (int i = 0; i < n; i++) copy(a[i], a[i] + n, b[i]); } inline void mulmat(const int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } inline void powmat(const int n, const mat a, long long b, mat c) { mat s, t; copymat(n, a, s); unitmat(n, c); while (b > 0) { if (b & 1) { mulmat(n, c, s, t); copymat(n, t, c); } mulmat(n, s, s, t); copymat(n, t, s); b >>= 1; } } inline void mulmatvec(const int n, const mat a, const vec b, vec c) { for (int i = 0; i < n; i++) { c[i] = 0; for (int j = 0; j < n; j++) c[i] += a[i][j] * b[j]; } } void printmat(const int n, const mat a) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) putchar(' '); printf("%d", a[i][j]); } putchar('\n'); } } /* main */ int main() { int a, b, c, d, e; ll n; scanf("%d%d%d%d%d%lld", &a, &b, &c, &d, &e, &n); mat ma = { { 0, 1, 0, 0 }, { d, c, e, 0 }, { 0, 0, 1, 0 }, { 0, 1, 0, 1 }, }; mat mb; powmat(M, ma, n, mb); vec va = { a, b, 1, a }, vb; mulmatvec(M, mb, va, vb); printf("%d\n", (int)vb[3]); return 0; }