#1169330 (C++23) No.3182 recurrence relation’s intersection sum

• 問題: No.3182 recurrence relation’s intersection sum
• ユーザー: iastm
• 提出日時: 2026-06-19 13:04:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 11,945 bytes
• コンパイル時間: 4,236 ms
• コンパイル使用メモリ: 219,204 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-06-19 13:04:52
• 合計ジャッジ時間: 5,074 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

#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
// #include <kotone/convolution_util>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_CONVOLUTION_UTIL_HPP
#define KOTONE_CONVOLUTION_UTIL_HPP 1

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


namespace kotone {

// Performs naive convolution of the specified formal power series.
// If either `fps_l` or `fps_r` is empty, returns an empty vector.
template <typename T> std::vector<T> naive_convolution(const std::vector<T> &fps_l, const std::vector<T> &fps_r) {
    if (fps_l.empty() || fps_r.empty()) return {};
    std::vector<T> result(fps_l.size() + fps_r.size() - 1);
    for (unsigned i{}; i < fps_l.size(); i++) {
        for (unsigned j{}; j < fps_r.size(); j++) {
            result[i + j] += fps_l[i] * fps_r[j];
        }
    }
    return result;
}

// Returns the inverse of the formal power series up to the first `n` coefficients.
// Requires `!fps.empty() && fps[0] != 0`.
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> inv_fps(const std::vector<mint> &fps, int n) {
    assert(n >= 0);
    assert(!fps.empty() && fps[0] != 0);
    if (n == 0) return {};
    std::vector<mint> result{1 / fps[0]};
    int m = 1;
    int len = static_cast<int>(fps.size());
    while (m < n) {
        m = std::min(m * 2, n);
        std::vector<mint> sub(fps.begin(), fps.begin() + std::min(m, len));
        if (m > len) sub.resize(m);
        std::vector<mint> prod = atcoder::convolution(result, sub);
        prod.resize(m);
        prod[0] = 2 - prod[0];
        for (int i = 1; i < m; i++) prod[i] = -prod[i];
        result = atcoder::convolution(result, prod);
        result.resize(m);
    }
    result.resize(n);
    return result;
}

// Returns the derivative of the formal power series.
// Returns an empty vector if `fps` is empty.
template <compatible_modint mint> std::vector<mint> derivative(const std::vector<mint> &fps) {
    if (fps.empty()) return {};
    std::vector<mint> result(fps.begin() + 1, fps.end());
    for (unsigned i{}; i < result.size(); i++) result[i] *= i + 1;
    return result;
}

// Returns the integral of the formal power series.
// Sets the integral's coefficient of the term independent of variables to `0`.
// If `fps` is empty, returns an empty vector.
template <compatible_modint mint> std::vector<mint> integral(const std::vector<mint> &fps) {
    if (fps.empty()) return {};
    int len = static_cast<int>(fps.size());
    std::vector<mint> result(len + 1);
    result[1] = 1;
    for (int i = 2; i <= len; i++) {
        result[i] = -result[mint::mod() % i] * mint(mint::mod() / i);
    }
    for (int i = 0; i < len; i++) result[i + 1] *= fps[i];
    return result;
}

// Returns the logarithm of the formal power series up to the first `n` coefficients.
// Requires `fps` to be non-empty and `fps[0] == 1`.
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> log_fps(const std::vector<mint> &fps, int n) {
    assert(!fps.empty());
    assert(fps[0] == 1);
    assert(n >= 0);
    if (n == 0) return {};
    std::vector<mint> dfps = derivative(fps), ifps = inv_fps(fps, n);
    std::vector<mint> prod = atcoder::convolution(dfps, ifps);
    prod.resize(n - 1);
    std::vector<mint> result = integral(prod);
    result.resize(n);
    return result;
}

// Returns the exponential of the formal power series up to the first `n` coefficients.
// If `fps` is empty, returns a vector of `n` elements filled with `0`.
// Requires `fps[0] == 0` if `fps` is not empty.
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> exp_fps(const std::vector<mint> &fps, int n) {
    assert(n >= 0);
    if (fps.empty()) return std::vector<mint>(n);
    assert(fps[0] == 0);
    if (n == 0) return {};
    std::vector<mint> result{1};
    int m = 1;
    while (m < n) {
        m = std::min(m * 2, n);
        std::vector<mint> log = log_fps(result, m);
        for (int i = 0; i < m; i++) {
            log[i] = -log[i];
            if (i < static_cast<int>(fps.size())) log[i] += fps[i];
        }
        log[0] += 1;
        result = atcoder::convolution(result, log);
        result.resize(m);
    }
    return result;
}

// Returns the formal power series raised to the specified power up to the first `n` coefficients.
// If `pow == 0`, the first element of the resulting vector is `1` and subsequence elements are `0`.
// If `pow > 0` and `fps` is empty, returns a vector of `n` elements filled with `0`.
// Requires `pow >= 0`.
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> pow_fps(const std::vector<mint> &fps, int64_t pow, int n) {
    assert(pow >= 0);
    assert(n >= 0);
    if (n == 0) return {};
    if (pow == 0) {
        std::vector<mint> result(n);
        result[0] = 1;
        return result;
    }
    int len = static_cast<int>(fps.size());
    int d = -1;
    for (int i = 0; i < len; i++) {
        if (fps[i] == 0) continue;
        d = i;
        break;
    }
    if (d == -1 || d > (n - 1) / pow) return std::vector<mint>(n);
    mint lead_coeff = fps[d];
    mint lead_pow = lead_coeff.pow(pow);
    mint lead_inv = 1 / lead_coeff;
    std::vector<mint> truncated_fps(fps.begin() + d, fps.end());
    for (mint &c : truncated_fps) c *= lead_inv;
    truncated_fps = log_fps(truncated_fps, n - d * pow);
    for (mint &c : truncated_fps) c *= pow;
    truncated_fps = exp_fps(truncated_fps, n - d * pow);
    for (mint &c : truncated_fps) c *= lead_pow;
    std::vector<mint> result(n);
    for (int i = 0; i + d * pow < n; i++) result[i + d * pow] = truncated_fps[i];
    return result;
}

// Computes the coefficient of the term with the specified degree `k` in the formal power series.
// Requires `!denominator.empty() && denominator[0] != 0`.
// Requires `k >= 0`.
// Reference: https://info.atcoder.jp/entry/algorithm_lectures/linearly_recurrent_sequence_kth_term
template <compatible_modint mint> mint bostan_mori(std::vector<mint> numerator, std::vector<mint> denominator, int64_t k) {
    assert(!denominator.empty() && denominator[0] != 0);
    assert(k >= 0);
    if (numerator.empty()) return 0;

    while (k) {
        std::vector<mint> denom_neg = denominator;
        for (unsigned i = 1; i < denom_neg.size(); i += 2) {
            denom_neg[i] = -denom_neg[i];
        }
        numerator = atcoder::convolution(numerator, denom_neg);
        denominator = atcoder::convolution(denominator, denom_neg);

        std::vector<mint> new_num, new_denom;
        for (unsigned i = k & 1; i < numerator.size(); i += 2) new_num.push_back(numerator[i]);
        for (unsigned i = 0; i < denominator.size(); i += 2) new_denom.push_back(denominator[i]);
        numerator = new_num;
        denominator = new_denom;
        k /= 2;
    }

    return numerator[0] / denominator[0];
}

// Computes term `a[k]` of a homogeneous linear recurrence `a` of order `n`.
// More specifically, `recurrence` specifies coefficients `c` in the relation
// `a[i] = c[0] * a[i - 1] + ... + c[n - 1] * a[i - n]`.
// Returns `0` if either `recurrence` or `init` is empty.
// Requires `recurrence.size() == init.size()`.
// Requires `k >= 0`.
template <compatible_modint mint> mint solve_recurrence(const std::vector<mint> &recurrence, const std::vector<mint> &init, int64_t k) {
    assert(recurrence.size() == init.size());
    assert(k >= 0);
    int n = int(recurrence.size());
    if (n == 0) return 0;
    if (k < n) return init[k];
    std::vector<mint> denominator(n + 1, 1);
    for (int i = 0; i < n; i++) denominator[i + 1] = -recurrence[i];
    std::vector<mint> numerator = atcoder::convolution(init, denominator);
    numerator.resize(n);
    return bostan_mori(numerator, denominator, k);
}

}  // namespace kotone

#endif  // KOTONE_CONVOLUTION_UTIL_HPP

using mint = atcoder::modint998244353;

int main() {
    int64_t K, L, R;
    std::cin >> K >> L >> R;
    R++;

    std::vector<mint> A{1};
    for (int i = 0; i < 300; i++) A.push_back(A.back() * K + mint(i).pow(K) + mint(K).pow(i));

    std::vector<mint> init(301);
    for (int i = 0; i < 300; i++) init[i + 1] = init[i] + A[i];
    std::vector<mint> rec = kotone::berlekamp_massey(init);
    init.resize(rec.size());
    mint result = kotone::solve_recurrence(rec, init, R) - kotone::solve_recurrence(rec, init, L);
    std::cout << result.val() << std::endl;
}