結果
| 問題 |
No.3228 Very Large Fibonacci Sum
|
| ユーザー |
 nonon
|
| 提出日時 | 2025-08-12 15:17:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 7,460 bytes |
| コンパイル時間 | 4,070 ms |
| コンパイル使用メモリ | 287,040 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-08-12 15:17:26 |
| 合計ジャッジ時間 | 5,118 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }
template<int MOD>
struct modint {
modint() : x(0) {}
modint(long long v) {
long long y = v % m();
if (y < 0) y += m();
x = (unsigned int)(y);
}
static modint raw(int v) {
modint a;
a.x = v;
return a;
}
static constexpr int mod() { return m(); }
unsigned int val() const { return x; }
modint& operator++() {
x++;
if (x == m()) x = 0;
return *this;
}
modint& operator--() {
if (x == 0) x = m();
x--;
return *this;
}
modint operator++(int) {
modint res = *this;
++*this;
return res;
}
modint operator--(int) {
modint res = *this;
--*this;
return res;
}
modint& operator+=(const modint &r) {
x += r.x;
if (x >= m()) x -= m();
return *this;
}
modint& operator-=(const modint &r) {
x -= r.x;
if (x >= m()) x += m();
return *this;
}
modint& operator*=(const modint &r) {
unsigned long long y = x;
y *= r.x;
x = (unsigned int)(y % m());
return *this;
}
modint &operator/=(const modint &r) {
return *this = *this * r.inv();
}
friend modint operator+(const modint &a, const modint &b) {
return modint(a) += b;
}
friend modint operator-(const modint &a, const modint &b) {
return modint(a) -= b;
}
friend modint operator*(const modint &a, const modint &b) {
return modint(a) *= b;
}
friend modint operator/(const modint &a, const modint &b) {
return modint(a) /= b;
}
friend bool operator==(const modint &a, const modint &b) {
return a.x == b.x;
}
friend bool operator!=(const modint &a, const modint &b) {
return a.x != b.x;
}
modint operator+() const { return *this; }
modint operator-() const { return modint() - *this; }
modint pow(long long k) const {
assert(k >= 0);
modint a = *this;
modint res = 1;
while (k > 0) {
if (k & 1) res *= a;
a *= a;
k >>= 1;
}
return res;
}
modint inv() const {
long long a = x, b = m(), u = 1, v = 0;
while (b > 0) {
long long t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
return modint(u);
}
private:
unsigned int x;
static constexpr unsigned int m() { return MOD; }
};
template<typename mint>
struct matrix : vector<vector<mint>> {
using vector<vector<mint>>::vector;
matrix(int h, int w) : vector<vector<mint>>(h, vector<mint>(w)) {}
matrix &operator*=(const mint &r) {
for (vector<mint> &v : *this) {
for (mint &a : v) a *= r;
}
return *this;
}
matrix &operator/=(const mint &r) {
mint invr = r.inv();
return *this *= invr;
}
matrix &operator+=(const matrix& a) {
assert(this->size() == a.size());
for (int i = 0; i < int(this->size()); i++) {
assert((*this)[i].size() == a[i].size());
for (int j = 0; j < int((*this)[i].size()); j++) {
(*this)[i][j] += a[i][j];
}
}
return *this;
}
matrix &operator-=(const matrix& a) {
assert(this->size() == a.size());
for (int i = 0; i < int(this->size()); i++) {
assert((*this)[i].size() == a[i].size());
for (int j = 0; j < int((*this)[i].size()); j++) {
(*this)[i][j] -= a[i][j];
}
}
return *this;
}
matrix &operator*=(const matrix &a) {
int n = this->size(), m = a.size();
assert(m >= 1);
int l = a[0].size();
matrix res(n, vector<mint>(l));
for (int i = 0; i < n; i++) {
assert(int((*this)[i].size()) == m);
for (int k = 0; k < m; k++) {
for (int j = 0; j < l; j++) {
res[i][j] += (*this)[i][k] * a[k][j];
}
}
}
return *this = res;
}
matrix operator*(const mint &r) const { return matrix(*this) *= r; }
matrix operator/(const mint &r) const { return matrix(*this) /= r; }
matrix operator+(const matrix &a) const { return matrix(*this) += a; }
matrix operator-(const matrix &a) const { return matrix(*this) -= a; }
matrix operator*(const matrix &a) const { return matrix(*this) *= a; }
static constexpr matrix I(int n) {
matrix res(n, n);
for (int i = 0; i < n; i++) {
res[i][i] = 1;
}
return res;
}
static constexpr matrix O(int n) { return matrix(n, n); }
matrix pow(long long k) const {
matrix res = I(this->size()), a = *this;
while (k > 0) {
if (k & 1) res *= a;
a *= a;
k >>= 1;
}
return res;
}
mint det() const {
int n = this->size();
assert(n >= 1);
assert((*this)[0].size() == this->size());
mint res = 1;
matrix a = *this;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (a[j][i] != 0) {
if (i != j) res = -res;
swap(a[i], a[j]);
break;
}
}
if (a[i][i] != 0) {
for (int j = i + 1; j < n; j++) {
mint inv = a[j][i] * a[i][i].inv();
for (int k = i + 1; k < n; k++) {
a[j][k] -= a[i][k] * inv;
}
}
}
}
for (int i = 0; i < n; i++) {
res *= a[i][i];
}
return res;
}
matrix inv() const {
int n = this->size();
matrix a = *this, res = I(n);
for (int i = 0; i < n; i++) {
if (a[i][i] == 0) {
for (int j = i + 1; j < n; j++) {
if (a[j][i] != 0) {
swap(a[i], a[j]);
swap(res[i], res[j]);
break;
}
}
}
assert(a[i][i] != 0);
mint cef = a[i][i].inv();
for (int j = 0; j < n; j++) {
a[i][j] *= cef;
res[i][j] *= cef;
}
for (int j = 0; j < n; j++) {
if (j != i) {
cef = a[j][i];
for (int k = 0; k < n; k++) {
a[j][k] -= a[i][k] * cef;
res[j][k] -= res[i][k] * cef;
}
}
}
}
return res;
}
};
using mint = modint<1000000007>;
using Mat = matrix<mint>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c, e, d;
cin >> a >> b >> c >> d >> e;
Mat A = {
{1, 1, 0, 0},
{0, c, d, e},
{0, 1, 0, 0},
{0, 0, 0, 1}
};
ll N;
cin >> N;
A = A.pow(N);
auto ans = A * Mat{
{a},
{b},
{a},
{1},
};
cout << ans[0][0].val() << endl;
}