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

• 問題: No.3182 recurrence relation’s intersection sum
• ユーザー: kwm_t
• 提出日時: 2026-03-21 13:49:14
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 4,165 bytes
• コンパイル時間: 4,409 ms
• コンパイル使用メモリ: 391,704 KB
• 実行使用メモリ: 7,720 KB
• 最終ジャッジ日時: 2026-03-21 13:49:25
• 合計ジャッジ時間: 5,848 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }


namespace kwm_t::math::fps {

// 線形漸化式の最小多項式を求める（Berlekamp-Massey法）
// A: 数列の先頭項, k次なら O(k^2)
// a_i = Σ(c_j * a_{i-j}) で表される数列に対して、{1,-c[1],-c[2],...} を返す
// 例: a_i = a[i-1]*3 + a[i-2]*1 -> {1,-3,-1}
template <typename T>
std::vector<T> BerlekampMassey(const std::vector<T> &A) {
	int M = A.size();
	T y = 1; // 直前の係数
	std::vector<T> B, C; // C は現在の多項式、B は直前の多項式
	B.reserve(M + 1);
	C.reserve(M + 1);
	B.push_back(T(1));
	C.push_back(T(1));

	for (int i = 1; i <= M; ++i) {
		int lc = C.size(), lb = B.size();
		T x = 0;
		for (int k = 0; k < lc; ++k) x += C[k] * A[i - lc + k];

		B.push_back(T(0));
		lb++;

		if (x == 0) continue;

		T Multi = x / y;

		if (lc < lb) {
			auto memo = C;
			if (lb > lc) C.insert(C.begin(), lb - lc, T(0));
			for (int k = 0; k < lb; ++k) C[k] -= Multi * B[k];
			B = memo;
			y = x;
		}
		else {
			for (int k = 0; k < lb; ++k)
				C[lc - 1 - k] -= Multi * B[lb - 1 - k];
		}
	}

	std::reverse(C.begin(), C.end());
	return C;
}

} // namespace kwm_t::math::fps


namespace kwm_t::math::fps {

// 二項生成関数の n 項目を高速に求める Bostan-Mori 法
template <class T>
struct Bostan_mori {
	std::vector<T> p, q;

	Bostan_mori(std::vector<T> &_p, std::vector<T> &_q) : p(_p), q(_q) {}

private:
	// f(x) -> f(-x) の符号反転（奇数項だけ反転）
	void rev(std::vector<T> &f) const {
		int d = f.size();
		for (int i = 0; i < d; ++i) if (i & 1) f[i] = -f[i];
	}

	// 偶数項抽出
	void even(std::vector<T> &f) const {
		int d = (f.size() + 1) >> 1;
		for (int i = 0; i < d; ++i) f[i] = f[i << 1];
		f.resize(d);
	}

	// 奇数項抽出
	void odd(std::vector<T> &f) const {
		int d = f.size() >> 1;
		for (int i = 0; i < d; ++i) f[i] = f[i << 1 | 1];
		f.resize(d);
	}

public:
	// n 項目を返す
	T operator[](long long n) const {
		std::vector<T> _p(p), _q(q), _q_rev(q);
		rev(_q_rev);

		for (; n; n >>= 1) {
			_p = atcoder::convolution(std::move(_p), _q_rev);
			if (n & 1) odd(_p);
			else       even(_p);

			_q = atcoder::convolution(std::move(_q), std::move(_q_rev));
			even(_q);
			_q_rev = _q;
			rev(_q_rev);
		}

		return _p[0] / _q[0];
	}
};

} // namespace kwm_t::math::fps

namespace kwm_t::math::fps {

// 線形漸化式の初めの d 項から n 項目を求める Bostan-Mori 用前処理
// d 次漸化式なら O(d^2 + d log d)
// a: 数列の先頭項（十分な長さ = 2*d程度）
template <typename T>
Bostan_mori<T> BM_BM(std::vector<T> a) {
	// 1. 最小多項式 q(x) を求める (O(d^2))
	auto q = BerlekampMassey(a);

	// 2. 多項式 p(x) を計算 (O(d log d))
	a.resize(q.size() - 1);
	auto p = atcoder::convolution(a, q);
	p.resize(q.size() - 1);

	// 3. Bostan-Mori 構造体を作成
	Bostan_mori<T> bm(p, q);
	return bm; // O(d log d log N) で任意項を取得可能
}

} // namespace kwm_t::math::fps
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	long long K, L, R; cin >> K >> L >> R;
	int n = 5000;
	std::vector<mint> a(n);
	a[0] = 1;
	for (int i = 1; i < n; i++) a[i] = a[i - 1] * K + mint(i - 1).pow(K) + mint(K).pow(i - 1);
	for (int i = 1; i < n; ++i) a[i] += a[i - 1];
	auto bm = kwm_t::math::fps::BM_BM(a);
	auto ans = bm[R] - (L ? bm[L - 1] : 0);
	cout << ans.val() << endl;
	return 0;
}