Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38846 Gapple 【S】T4 C++ 编译错误 0 0 MS 0 KB 2679 2025-11-06 19:38:11

Tests(0/0):


#pragma GCC optimize("Ofast,no-stack-protector,inline,fast-math,unroll-loops") #include <atcoder/convolution> #include <atcoder/modint> #include <iostream> #include <vector> using namespace std; using i64 = long long; constexpr int N = 3000, MOD = 998244353; using mint = atcoder::static_modint<MOD>; template <class T, int deg> struct ModPoly { int nxt; vector<T> terms; ModPoly(int nxt = 1) : nxt(nxt) , terms(deg + 1) { } ModPoly(const vector<T>& coeff, int nxt = 1) : nxt(nxt) , terms(coeff) { terms.resize(deg); } T& operator[](int power) { return terms[power]; } const T& operator[](int power) const { return terms[power]; } friend ModPoly operator+(const ModPoly& lhs, const ModPoly& rhs) { ModPoly res = lhs; for (int i = 0; i <= deg; i += rhs.nxt) res[i] += rhs[i]; return res; } friend ModPoly operator-(const ModPoly& lhs, const ModPoly& rhs) { ModPoly res = lhs; for (int i = 0; i <= deg; i += rhs.nxt) res[i] -= rhs[i]; return res; } ModPoly operator-() const { return ModPoly() - *this; } friend ModPoly operator*(const ModPoly& lhs, const ModPoly& rhs) { return atcoder::convolution(lhs.terms, rhs.terms); } friend ModPoly& operator+=(ModPoly& lhs, const ModPoly& rhs) { return lhs = lhs + rhs; } friend ModPoly& operator-=(ModPoly& lhs, const ModPoly& rhs) { return lhs = lhs - rhs; } friend ModPoly& operator*=(ModPoly& lhs, const ModPoly& rhs) { return lhs = lhs * rhs; } }; mint inv[N + 1], fact[N + 1], ifact[N + 1]; void prepare() { inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1; for (int i = 2; i <= N; ++i) { inv[i] = inv[MOD % i] * (MOD - MOD / i); fact[i] = fact[i - 1] * i; ifact[i] = ifact[i - 1] * inv[i]; } } ModPoly<mint, N> g; mint solve(int n, int k) { ModPoly<mint, N> f(k); for (int i = k; i <= n; i += k) f[i] = ifact[i].pow(n); f = -f; auto ans = g, pow_f = f; for (int i = 0; i < (n + k - 1) / k; ++i) { ans += g * pow_f; pow_f *= f; } return ((n + k - 1) / k % 2 == 0 ? -1 : 1) * fact[n].pow(n) * ans[n]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, l, r; cin >> n >> l >> r; prepare(); for (int i = 1; i <= n; ++i) g[i] = ifact[i].pow(n); for (int i = l; i <= r; ++i) cout << solve(n, i).val() << ' '; return 0; }


测评信息: