結果
| 問題 | No.3228 Very Large Fibonacci Sum |
| コンテスト | |
| ユーザー |
 joji
|
| 提出日時 | 2026-01-21 22:10:25 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,061 bytes |
| 記録 | |
| コンパイル時間 | 4,118 ms |
| コンパイル使用メモリ | 350,300 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2026-01-21 22:10:31 |
| 合計ジャッジ時間 | 4,746 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#line 1 "3228.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3228"
#line 2 "ds/matrix.hpp"
#include <cassert>
#include <cstdint>
#include <vector>
template <typename T> struct Matrix {
int H, W;
std::vector<std::vector<T>> table;
Matrix(int h, int w) : H(h), W(w), table(h, std::vector<T>(w)) {}
Matrix(const std::vector<std::vector<T>> &v) : H((int)v.size()), W((int)v[0].size()), table(v) {}
std::vector<T> &operator[](int i) { return table[i]; }
const std::vector<T> &operator[](int i) const { return table[i]; }
static Matrix identity(int N) {
Matrix res(N, N);
for (int i = 0; i < N; i++) {
res[i][i] = 1;
}
return res;
}
Matrix &operator+=(const Matrix &rhs) {
assert(H == rhs.H && W == rhs.W && "DIMENSION must be the same");
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
table[i][j] += rhs[i][j];
}
}
return *this;
}
Matrix &operator-=(const Matrix &rhs) {
assert(H == rhs.H && W == rhs.W && "DIMENSION must be the same");
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
table[i][j] -= rhs[i][j];
}
}
return *this;
}
Matrix operator*(const Matrix &rhs) const {
assert(W == rhs.H && "MULTIPLICATION DIMENSION does not match");
Matrix res(H, rhs.W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (table[i][j] == 0) continue;
for (int k = 0; k < rhs.W; k++) {
res[i][k] += table[i][j] * rhs[j][k];
}
}
}
return res;
}
Matrix &operator*=(const Matrix &rhs) { return *this = *this * rhs; }
Matrix pow(int64_t n) const {
assert(H == W && "DIMENSION must be square");
Matrix res = identity(H);
Matrix a = *this;
while (n > 0) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
};
#line 3 "mod/modint.hpp"
#include <iostream>
#include <utility>
template <uint32_t MOD> struct ModInt {
static_assert(MOD > 1, "MOD must be > 1");
uint32_t val;
constexpr ModInt() : val(0) {}
constexpr ModInt(const int64_t &x) : val(x >= 0 ? x % MOD : (MOD - (-x) % MOD) % MOD) {}
constexpr uint32_t value() const { return val; }
constexpr ModInt &operator+=(const ModInt &rhs) {
val += rhs.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr ModInt &operator-=(const ModInt &rhs) {
if (val < rhs.val) val += MOD;
val -= rhs.val;
return *this;
}
constexpr ModInt &operator*=(const ModInt &rhs) {
val = (uint64_t)val * rhs.val % MOD;
return *this;
}
constexpr ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inverse(); }
constexpr ModInt operator+() const { return *this; }
constexpr ModInt operator-() const { return ModInt(val == 0 ? 0 : MOD - val); }
friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) { return lhs += rhs; }
friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) { return lhs -= rhs; }
friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) { return lhs *= rhs; }
friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) { return lhs /= rhs; }
friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val == rhs.val; }
friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.val != rhs.val; }
constexpr ModInt pow(uint64_t n) const {
ModInt res = 1, a = *this;
while (n > 0) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
constexpr ModInt inverse() const {
int64_t a = val, b = MOD, u = 1, v = 0;
while (b) {
int64_t t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return ModInt(u);
}
friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }
friend std::istream &operator>>(std::istream &is, ModInt &x) {
int64_t v;
is >> v;
x = ModInt(v);
return is;
}
};
#line 4 "3228.test.cpp"
#include <bits/stdc++.h>
using namespace std;
void solve() {
int64_t a, b, c, d, e, N;
cin >> a >> b >> c >> d >> e >> N;
using Mint = ModInt<1000000007>;
if (N < 2) {
Mint out = (N ? a + b : a);
cout << out << '\n';
return;
}
Matrix<Mint> transition(4, 4), base(4, 1);
transition.table = {{c, d, 0, e}, {1, 0, 0, 0}, {c, d, 1, e}, {0, 0, 0, 1}};
base.table = {{b}, {a}, {Mint(a + b)}, {1}};
Matrix<Mint> res = transition.pow(N - 1) * base;
cout << res[2][0] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}