結果
| 問題 |
No.3228 Very Large Fibonacci Sum
|
| コンテスト | |
| ユーザー |
 だれ
|
| 提出日時 | 2025-08-08 22:37:09 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 12,534 bytes |
| コンパイル時間 | 3,989 ms |
| コンパイル使用メモリ | 228,792 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-08-08 22:37:15 |
| 合計ジャッジ時間 | 5,071 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define UNIQUE(x) \
std::sort((x).begin(), (x).end()); \
(x).erase(std::unique((x).begin(), (x).end()), (x).end())
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i32 = int;
using ld = long double;
using f64 = double;
template <class T, class U>
bool chmin(T& a, const U& b) {
return (b < a) ? (a = b, true) : false;
}
template <class T, class U>
bool chmax(T& a, const U& b) {
return (b > a) ? (a = b, true) : false;
}
template <class T = std::string, class U = std::string>
inline void YesNo(bool f = 0, const T yes = "Yes", const U no = "No") {
if (f)
std::cout << yes << "\n";
else
std::cout << no << "\n";
}
namespace io {
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
i >> p.first >> p.second;
return i;
}
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
o << p.first << " " << p.second;
return o;
}
template <typename T>
istream& operator>>(istream& i, vector<T>& v) {
rep(j, v.size()) i >> v[j];
return i;
}
template <typename T>
string join(vector<T>& v) {
stringstream s;
rep(i, v.size()) s << ' ' << v[i];
return s.str().substr(1);
}
template <typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
if (v.size()) o << join(v);
return o;
}
template <typename T>
string join(vector<vector<T>>& vv) {
string s = "\n";
rep(i, vv.size()) s += join(vv[i]) + "\n";
return s;
}
template <typename T>
ostream& operator<<(ostream& o, vector<vector<T>>& vv) {
if (vv.size()) o << join(vv);
return o;
}
void OUT() { std::cout << "\n"; }
template <class Head, class... Tail>
void OUT(Head&& head, Tail&&... tail) {
std::cout << head;
if (sizeof...(tail)) std::cout << ' ';
OUT(std::forward<Tail>(tail)...);
}
void OUTL() { std::cout << std::endl; }
template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
std::cout << head;
if (sizeof...(tail)) std::cout << ' ';
OUTL(std::forward<Tail>(tail)...);
}
void IN() {}
template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
cin >> head;
IN(std::forward<Tail>(tail)...);
}
} // namespace io
using namespace io;
namespace useful {
long long modpow(long long a, long long b, long long mod) {
long long res = 1;
while (b) {
if (b & 1) res *= a, res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}
bool is_pow2(long long x) { return x > 0 && (x & (x - 1)) == 0; }
template <class T>
void rearrange(vector<T>& a, vector<int>& p) {
vector<T> b = a;
for (int i = 0; i < int(a.size()); i++) {
a[i] = b[p[i]];
}
return;
}
template <std::forward_iterator I>
std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
run_length_encoding(I s, I t) {
if (s == t) return {};
std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
res;
res.emplace_back(*s, 1);
for (auto it = ++s; it != t; it++) {
if (*it == res.back().first)
res.back().second++;
else
res.emplace_back(*it, 1);
}
return res;
}
vector<int> linear_sieve(int n) {
vector<int> primes;
vector<int> res(n + 1);
iota(all(res), 0);
for (int i = 2; i <= n; i++) {
if (res[i] == i) primes.emplace_back(i);
for (auto j : primes) {
if (j * i > n) break;
res[j * i] = j;
}
}
return res;
// return primes;
}
template <class T>
vector<long long> dijkstra(vector<vector<pair<int, T>>>& graph, int start) {
int n = graph.size();
vector<long long> res(n, 2e18);
res[start] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<pair<long long, int>>>
que;
que.push({0, start});
while (!que.empty()) {
auto [c, v] = que.top();
que.pop();
if (res[v] < c) continue;
for (auto [nxt, cost] : graph[v]) {
auto x = c + cost;
if (x < res[nxt]) {
res[nxt] = x;
que.push({x, nxt});
}
}
}
return res;
}
} // namespace useful
using namespace useful;
template <class T, T l, T r>
struct RandomIntGenerator {
std::random_device seed;
std::mt19937_64 engine;
std::uniform_int_distribution<T> uid;
RandomIntGenerator() {
engine = std::mt19937_64(seed());
uid = std::uniform_int_distribution<T>(l, r);
}
T gen() { return uid(engine); }
};
#include <algorithm>
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
template <class R>
struct Matrix {
int H, W;
std::vector<std::vector<R>> A;
Matrix(int h, int w) : H(h), W(w), A(std::vector(h, std::vector<R>(w))) {}
Matrix(int n) : Matrix(n, n) {}
Matrix(const std::vector<std::vector<R>>& a)
: H(a.size()), W(a[0].size()), A(a) {}
inline const std::vector<R>& operator[](int i) const { return A[i]; }
inline std::vector<R>& operator[](int i) { return A[i]; }
void swap_row(int i, int j) { std::swap(A[i], A[j]); }
void swap_column(int i, int j) {
for (int k = 0; k < H; k++) {
std::swap(A[k][i], A[k][j]);
}
}
Matrix& operator+=(const Matrix& B) {
assert(H == B.H && W == B.W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
A[i][j] += B[i][j];
}
}
return *this;
}
Matrix& operator-=(const Matrix& B) {
assert(H == B.H && W == B.W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
A[i][j] += B[i][j];
}
}
return *this;
}
Matrix& operator*=(const Matrix& B) {
assert(W == B.H);
std::vector C(H, std::vector<R>(B.W, R(0)));
for (int i = 0; i < H; i++) {
for (int k = 0; k < W; k++) {
for (int j = 0; j < B.W; j++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
A.swap(C);
W = B.W;
return (*this);
}
Matrix operator+(const Matrix& B) const { return Matrix(*this) += B; }
Matrix operator-(const Matrix& B) const { return Matrix(*this) -= B; }
Matrix operator*(const Matrix& B) const { return Matrix(*this) *= B; }
bool operator==(const Matrix& B) const {
if (H != B.H || W != B.W) return false;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (A[i][j] != B[i][j]) return false;
}
}
return true;
}
friend std::ostream& operator<<(std::ostream& os, const Matrix& B) {
for (int i = 0; i < B.H; i++) {
for (int j = 0; j < B.W; j++) {
os << B[i][j] << (j == B.W - 1 ? "\n" : " ");
}
}
return os;
}
// return {rank, det}
static std::pair<int, R> GaussElimination(Matrix& a, int pivot_end = -1,
bool diagonalize = false) {
int h = a.H, w = a.W, rank = 0;
if (pivot_end == -1) pivot_end = w;
R det = 1;
for (int j = 0; j < pivot_end; j++) {
int idx = -1;
for (int i = rank; i < h; i++) {
if (a[i][j] != R(0)) {
idx = i;
break;
}
}
if (idx == -1) {
det = 0;
continue;
}
if (rank != idx) {
det = -det;
a.swap_row(rank, idx);
}
det *= a[rank][j];
if (diagonalize && a[rank][j] != R(1)) {
R cr = R(1) / a[rank][j];
for (int k = j; k < w; k++) a[rank][k] *= cr;
}
int is = diagonalize ? 0 : rank + 1;
for (int i = is; i < h; i++) {
if (i == rank) continue;
if (a[i][j] != R(0)) {
R cr = a[i][j] / a[rank][j];
for (int k = j; k < w; k++) a[i][k] -= a[rank][k] * cr;
}
}
rank++;
}
return std::make_pair(rank, det);
}
std::pair<std::vector<R>, std::vector<std::vector<R>>> LinearEquation(
std::vector<R> b) {
assert(H == (int)b.size());
Matrix<R> M = Matrix(*this);
for (int i = 0; i < H; i++) M[i].push_back(b[i]);
M.W++;
auto [rank, _] = Matrix<R>::GaussElimination(M, W, true);
for (int i = rank; i < H; i++) {
if (M[i][W] != R(0))
return std::make_pair(std::vector<R>(),
std::vector<std::vector<R>>());
}
std::vector<R> sol(W, 0);
std::vector<std::vector<R>> basis;
std::vector<int> pivot(W, -1);
for (int i = 0, j = 0; i < rank; i++) {
while (M[i][j] == R(0)) j++;
sol[j] = M[i][W], pivot[j] = i;
}
for (int j = 0; j < W; j++) {
if (pivot[j] == -1) {
std::vector<R> x(W);
x[j] = 1;
for (int k = 0; k < j; k++) {
if (pivot[k] != -1) x[k] = -M[pivot[k]][j];
}
basis.emplace_back(x);
}
}
return std::make_pair(sol, basis);
}
};
template <class R>
struct SquareMatrix : Matrix<R> {
int N;
SquareMatrix(int n_) : Matrix<R>(n_, n_), N(n_) {}
SquareMatrix<R> inverse() const {
Matrix<R> m(N, 2 * N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
m[i][j] = this->A[i][j];
}
m[i][N + i] = R(1);
}
auto [rank, det] = Matrix<R>::GaussElimination(m, N, true);
if (rank != N) return SquareMatrix<R>(0);
SquareMatrix<R> res(N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res[i][j] = m[i][N + j];
}
}
return res;
}
R determinant() {
Matrix M = Matrix(*this);
auto [rank, det] = Matrix<R>::GaussElimination(M);
return det;
}
static SquareMatrix<R> I(int n) {
SquareMatrix<R> res(n);
for (int i = 0; i < n; i++) res[i][i] = R(1);
return res;
}
SquareMatrix<R> pow(unsigned long long x) {
SquareMatrix<R> res = SquareMatrix<R>::I(N);
auto a = SquareMatrix(*this);
while (x > 0) {
if (x & 1) res *= a;
a *= a;
x >>= 1;
}
return res;
}
R cofactor(int x, int y) {
SquareMatrix<R> a(N - 1);
for (int i = 0; i < N; i++) {
if (i == x) continue;
for (int j = 0; j < N; j++) {
if (j == y) continue;
a[i - (i > x)][j - (j > y)] = this->A[i][j];
}
}
R res = a.determinant();
if ((x + y) & 1) res = -res;
return res;
}
};
using mint = atcoder::modint1000000007;
int main() {
std::cout << fixed << setprecision(15);
cin.tie(nullptr);
ios::sync_with_stdio(false);
i64 a, b, c, d, e, n;
IN(a, b, c, d, e, n);
if (n == 0) {
OUT(mint(a).val());
return 0;
}
Matrix<mint> x0(4, 1);
x0[0][0] = b;
x0[1][0] = a;
x0[2][0] = 1;
x0[3][0] = a + b;
SquareMatrix<mint> M(4);
M[0][0] = M[3][0] = c;
M[0][1] = M[3][1] = d;
M[0][2] = M[3][2] = e;
M[1][0] = M[2][2] = M[3][3] = 1;
M = M.pow(n - 1);
auto y = M * x0;
OUT(y[3][0].val());
}