#include #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_BERLEKAMP_MASSEY_HPP #define KOTONE_BERLEKAMP_MASSEY_HPP 1 #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP #define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1 #include namespace kotone { template concept number = std::is_arithmetic_v; template concept signed_number = std::signed_integral || std::floating_point; template concept compatible_modint = requires(mint a, mint b, int64_t x) { { mint::mod() } -> std::convertible_to; mint{}; mint{1}; mint{x}; { a + b } -> std::same_as; { a - b } -> std::same_as; { -a } -> std::same_as; { a * b } -> std::same_as; { a / b } -> std::same_as; { a.inv() } -> std::same_as; { a.pow(x) } -> std::same_as; { a += b } -> std::same_as; { a -= b } -> std::same_as; { a *= b } -> std::same_as; { a /= b } -> std::same_as; { a == b } -> std::convertible_to; { a != b } -> std::convertible_to; { a.val() } -> std::convertible_to; }; template concept additive = requires(T a, T b) { T{}; { a + b } -> std::same_as; { a - b } -> std::same_as; { -a } -> std::same_as; { a == b } -> std::convertible_to; { a != b } -> std::convertible_to; }; template concept mutable_additive = ( additive && requires(T a, T b) { { a += b } -> std::same_as; { a -= b } -> std::same_as; { ++a } -> std::same_as; { --a } -> std::same_as; { a++ } -> std::same_as; { a-- } -> std::same_as; } ); } // 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 std::vector berlekamp_massey(const std::vector &vec) { assert(vec.size() <= 100000000u); int len = static_cast(vec.size()); std::vector 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 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 // https://github.com/amiast/cpp-utility #ifndef KOTONE_CONVOLUTION_UTIL_HPP #define KOTONE_CONVOLUTION_UTIL_HPP 1 #include #include #include // #include // 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 std::vector naive_convolution(const std::vector &fps_l, const std::vector &fps_r) { if (fps_l.empty() || fps_r.empty()) return {}; std::vector 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 std::vector inv_fps(const std::vector &fps, int n) { assert(n >= 0); assert(!fps.empty() && fps[0] != 0); if (n == 0) return {}; std::vector result{1 / fps[0]}; int m = 1; int len = static_cast(fps.size()); while (m < n) { m = std::min(m * 2, n); std::vector sub(fps.begin(), fps.begin() + std::min(m, len)); if (m > len) sub.resize(m); std::vector 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 std::vector derivative(const std::vector &fps) { if (fps.empty()) return {}; std::vector 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 std::vector integral(const std::vector &fps) { if (fps.empty()) return {}; int len = static_cast(fps.size()); std::vector 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 std::vector log_fps(const std::vector &fps, int n) { assert(!fps.empty()); assert(fps[0] == 1); assert(n >= 0); if (n == 0) return {}; std::vector dfps = derivative(fps), ifps = inv_fps(fps, n); std::vector prod = atcoder::convolution(dfps, ifps); prod.resize(n - 1); std::vector 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 std::vector exp_fps(const std::vector &fps, int n) { assert(n >= 0); if (fps.empty()) return std::vector(n); assert(fps[0] == 0); if (n == 0) return {}; std::vector result{1}; int m = 1; while (m < n) { m = std::min(m * 2, n); std::vector log = log_fps(result, m); for (int i = 0; i < m; i++) { log[i] = -log[i]; if (i < static_cast(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 std::vector pow_fps(const std::vector &fps, int64_t pow, int n) { assert(pow >= 0); assert(n >= 0); if (n == 0) return {}; if (pow == 0) { std::vector result(n); result[0] = 1; return result; } int len = static_cast(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(n); mint lead_coeff = fps[d]; mint lead_pow = lead_coeff.pow(pow); mint lead_inv = 1 / lead_coeff; std::vector 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 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 mint bostan_mori(std::vector numerator, std::vector denominator, int64_t k) { assert(!denominator.empty() && denominator[0] != 0); assert(k >= 0); if (numerator.empty()) return 0; while (k) { std::vector 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 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 mint solve_recurrence(const std::vector &recurrence, const std::vector &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 denominator(n + 1, 1); for (int i = 0; i < n; i++) denominator[i + 1] = -recurrence[i]; std::vector 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 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 init(301); for (int i = 0; i < 300; i++) init[i + 1] = init[i] + A[i]; std::vector 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; }