#1169327 (C++23) No.3228 Very Large Fibonacci Sum

• 問題: No.3228 Very Large Fibonacci Sum
• ユーザー: iastm
• 提出日時: 2026-06-19 12:53:52
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 5,041 bytes
• コンパイル時間: 1,313 ms
• コンパイル使用メモリ: 177,804 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-06-19 12:53:56
• 合計ジャッジ時間: 2,642 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

#include <iostream>
#include <vector>
#include <atcoder/modint>
// #include <kotone/berlekamp_massey>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_BERLEKAMP_MASSEY_HPP
#define KOTONE_BERLEKAMP_MASSEY_HPP 1

#include <vector>
#include <cassert>
// #include <kotone/internal_type_traits>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP
#define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1

#include <concepts>

namespace kotone {

template <typename T> concept number = std::is_arithmetic_v<T>;

template <typename T> concept signed_number = std::signed_integral<T> || std::floating_point<T>;

template <typename mint> concept compatible_modint = requires(mint a, mint b, int64_t x) {
    { mint::mod() } -> std::convertible_to<int>;
    mint{};
    mint{1};
    mint{x};

    { a + b }       -> std::same_as<mint>;
    { a - b }       -> std::same_as<mint>;
    { -a }          -> std::same_as<mint>;
    { a * b }       -> std::same_as<mint>;
    { a / b }       -> std::same_as<mint>;
    { a.inv() }     -> std::same_as<mint>;
    { a.pow(x) }    -> std::same_as<mint>;

    { a += b }      -> std::same_as<mint&>;
    { a -= b }      -> std::same_as<mint&>;
    { a *= b }      -> std::same_as<mint&>;
    { a /= b }      -> std::same_as<mint&>;

    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
    { a.val() }     -> std::convertible_to<int>;
};

template <typename T> concept additive = requires(T a, T b) {
    T{};
    { a + b }       -> std::same_as<T>;
    { a - b }       -> std::same_as<T>;
    { -a }          -> std::same_as<T>;
    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
};

template <typename T> concept mutable_additive = (
    additive<T>
    && requires(T a, T b) {
        { a += b }  -> std::same_as<T&>;
        { a -= b }  -> std::same_as<T&>;
        { ++a }     -> std::same_as<T&>;
        { --a }     -> std::same_as<T&>;
        { a++ }     -> std::same_as<T>;
        { a-- }     -> std::same_as<T>;
    }
);

}  // namespace kotone

#endif  // KOTONE_INTERNAL_TYPE_TRAITS

namespace kotone {

// Returns a vector containing the minimum number of coefficients of the recurrence relation
// given the specified initial condition in `vec`.
template <compatible_modint mint> std::vector<mint> berlekamp_massey(const std::vector<mint> &vec) {
    assert(vec.size() <= 100000000u);
    int len = static_cast<int>(vec.size());
    std::vector<mint> coeffs{1}, last_coeffs{1};
    int curr_len = 0, num_steps = 1;
    mint last_diff = 1;
    for (int i = 0; i < len; i++) {
        mint diff = vec[i];
        for (int j = 1; j <= curr_len; j++) diff += coeffs[j] * vec[i - j];
        if (diff == 0) {
            num_steps++;
            continue;
        }
        std::vector<mint> temp = coeffs;
        mint factor = diff / last_diff;
        if (coeffs.size() < last_coeffs.size() + num_steps) {
            coeffs.resize(last_coeffs.size() + num_steps);
        }
        for (unsigned j{}; j < last_coeffs.size(); j++) {
            coeffs[j + num_steps] -= factor * last_coeffs[j];
        }
        if (curr_len * 2 <= i) {
            last_coeffs = temp;
            curr_len = i + 1 - curr_len;
            last_diff = diff;
            num_steps = 1;
        } else {
            num_steps++;
        }
    }
    coeffs.erase(coeffs.begin());
    for (mint &c : coeffs) c = -c;
    return coeffs;
}

}  // namespace kotone

#endif  // KOTONE_BERLEKAMP_MASSEY_HPP

using mint = atcoder::modint1000000007;

std::vector<std::vector<mint>> prod(const std::vector<std::vector<mint>> &a, const std::vector<std::vector<mint>> &b) {
    int n = a.size(), m = b.size(), l = b[0].size();
    std::vector result(n, std::vector<mint>(l));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            for (int j = 0; j < l; j++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}

std::vector<std::vector<mint>> pow(const std::vector<std::vector<mint>> &a, int64_t k) {
    if (k <= 1) return a;
    std::vector<std::vector<mint>> result = pow(a, k / 2);
    result = prod(result, result);
    if (k % 2 == 1) result = prod(result, a);
    return result;
}

int main() {
    int a, b, c, d, e;
    int64_t N;
    std::cin >> a >> b >> c >> d >> e >> N;
    std::vector<mint> init{a, b};
    for (int i = 2; i < 10; i++) init.push_back(init[i - 1] * c + init[i - 2] * d + e);
    for (int i = 0; i < 9; i++) init[i + 1] += init[i];

    if (N < 10) {
        std::cout << init[N].val() << std::endl;
        return 0;
    }

    std::vector<mint> rec = kotone::berlekamp_massey(init);
    int K = rec.size();
    std::vector mat(K, std::vector<mint>(K));
    mat[0] = rec;
    for (int i = 1; i < K; i++) mat[i][i - 1] = 1;
    mint result = 0;
    auto exp = pow(mat, N - (K - 1));
    for (int i = 0; i < K; i++) result += exp[0][i] * init[K - 1 - i];
    std::cout << result.val() << std::endl;
}