This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/stirling_number_of_the_first_kind
#include "../../Series.cpp"
void solve() {
using mint = atcoder::modint998244353;
int n;
cin >> n;
Binomial<mint> bin(n);
auto f = stirling_first(n, bin);
for (auto x : f) cout << x.val() << " ";
cout << endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
solve();
}
#line 1 "test/Series/StirlingFirst.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/stirling_number_of_the_first_kind
#line 1 "Binomial.cpp"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Binomial {
vector<T> inv, fact, factinv;
Binomial(int n) {
inv.resize(n + 1);
fact.resize(n + 1);
factinv.resize(n + 1);
inv[0] = fact[0] = factinv[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
factinv[n] = fact[n].inv();
inv[n] = fact[n - 1] * factinv[n];
for (int i = n - 1; i >= 1; i--) {
factinv[i] = factinv[i + 1] * (i + 1);
inv[i] = fact[i - 1] * factinv[i];
}
}
T C(int n, int r) {
if (n < 0 || n < r || r < 0) return 0;
return fact[n] * factinv[n - r] * factinv[r];
}
T P(int n, int r) {
if (n < 0 || n < r || r < 0) return 0;
return fact[n] * factinv[n - r];
}
T H(int n, int r) {
if (n == 0 && r == 0) return 1;
if (n < 0 || r < 0) return 0;
return r == 0 ? 1 : C(n + r - 1, r);
}
};
#line 1 "FormalPowerSeries.cpp"
#include <atcoder/convolution>
#line 2 "template.cpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <class T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using pbds_mset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pbds_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T, class U>
inline bool chmax(T &a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T, class U>
inline bool chmin(T &a, U b) {
if (a > b) {
a = b;
return true;
}
return false;
}
constexpr int INF = 1000000000;
constexpr int64_t llINF = 3000000000000000000;
constexpr double eps = 1e-10;
const double pi = acos(-1);
template <class T>
inline void compress(vector<T> &a) {
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
struct linear_sieve {
vector<int> least_factor, prime_list;
linear_sieve(int n) : least_factor(n + 1, 0) {
for (int i = 2; i <= n; i++) {
if (least_factor[i] == 0) {
least_factor[i] = i;
prime_list.push_back(i);
}
for (int p : prime_list) {
if (ll(i) * p > n || p > least_factor[i]) break;
least_factor[i * p] = p;
}
}
}
};
ll extgcd(ll a, ll b, ll &x, ll &y) {
// ax+by=gcd(|a|,|b|)
if (a < 0 || b < 0) {
ll d = extgcd(abs(a), abs(b), x, y);
if (a < 0) x = -x;
if (b < 0) y = -y;
return d;
}
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll d = extgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll modpow(ll a, ll b, ll m) {
ll res = 1;
while (b) {
if (b & 1) {
res *= a;
res %= m;
}
a *= a;
a %= m;
b >>= 1;
}
return res;
}
template <typename T, typename U>
inline istream &operator>>(istream &is, pair<T, U> &rhs) {
return is >> rhs.first >> rhs.second;
}
template <typename T>
inline istream &operator>>(istream &is, vector<T> &v) {
for (auto &e : v) is >> e;
return is;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
return os << rhs.first << " " << rhs.second;
}
template <typename T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {
os << *itr;
if (++itr != end_itr) os << " ";
}
return os;
}
#line 2 "mod_sqrt.cpp"
int64_t mod_sqrt(const int64_t& a, const int64_t& p) {
assert(0 <= a && a < p);
if (a < 2) return a;
if (modpow(a, (p - 1) >> 1, p) != 1) return -1;
int64_t q = p - 1, m = 0;
while (!(q & 1)) {
q >>= 1;
m++;
}
int64_t z = 1;
while (modpow(z, (p - 1) >> 1, p) == 1) z++;
int64_t c = modpow(z, q, p);
int64_t t = modpow(a, q, p);
int64_t r = modpow(a, (q + 1) >> 1, p);
if (t == 0) return 0;
m -= 2;
while (t != 1) {
while (modpow(t, int64_t(1) << m, p) == 1) {
c = c * c % p;
m--;
}
r = r * c % p;
c = c * c % p;
t = t * c % p;
m--;
}
return r;
}
#line 3 "FormalPowerSeries.cpp"
template <typename mint>
struct FormalPowerSeries : vector<mint> {
using vector<mint>::vector;
using FPS = FormalPowerSeries;
FPS& operator+=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
return *this;
}
FPS& operator+=(const mint& r) {
if (this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
FPS& operator-=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
return *this;
}
FPS& operator-=(const mint& r) {
if (this->empty()) this->resize(1);
(*this)[0] -= r;
return *this;
}
FPS& operator*=(const FPS& r) {
if (this->empty() || r.empty()) {
this->clear();
return *this;
}
assert(mint::mod() == 998244353);
vector<mint> prod = atcoder::convolution(*this, r);
this->resize((int)prod.size());
for (int i = 0; i < (int)this->size(); i++) (*this)[i] = prod[i];
return *this;
}
FPS& operator*=(const mint& v) {
for (int i = 0; i < (int)this->size(); i++) (*this)[i] *= v;
return *this;
}
FPS& operator/=(const FPS& r) {
if (this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev();
}
FPS& operator%=(const FPS& r) {
*this -= *this / r * r;
shrink();
return *this;
}
FPS operator+(const FPS& r) const { return FPS(*this) += r; }
FPS operator+(const mint& v) const { return FPS(*this) += v; }
FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
FPS operator-(const mint& v) const { return FPS(*this) -= v; }
FPS operator*(const FPS& r) const { return FPS(*this) *= r; }
FPS operator*(const mint& v) const { return FPS(*this) *= v; }
FPS operator/(const FPS& r) const { return FPS(*this) /= r; }
FPS operator%(const FPS& r) const { return FPS(*this) %= r; }
FPS operator-() const {
FPS ret(this->size());
for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
void shrink() {
while (this->size() && this->back() == mint(0)) this->pop_back();
}
FPS operator>>(int sz) const {
if ((int)this->size() <= sz) return {};
FPS ret(*this);
ret.erase(ret.begin(), ret.begin() + sz);
return ret;
}
FPS operator<<(int sz) const {
FPS ret(*this);
ret.insert(ret.begin(), sz, mint(0));
return ret;
}
FPS pre(int sz) const { return FPS(begin(*this), begin(*this) + min((int)this->size(), sz)); }
FPS rev() const {
FPS ret(*this);
reverse(begin(ret), end(ret));
return ret;
}
FPS diff() const {
const int n = this->size();
FPS ret(max(0, n - 1));
for (int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * mint(i);
return ret;
}
FPS integral() const {
const int n = this->size();
FPS ret(n + 1);
ret[0] = mint(0);
if (n > 0) ret[1] = mint(1);
auto mod = mint::mod();
for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i] * (mod / i));
for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
return ret;
}
FPS inv(int deg = -1) const {
assert(((*this)[0]) != mint(0));
const int n = this->size();
if (deg == -1) deg = n;
FPS ret({mint(1) / (*this)[0]});
for (int i = 1; i < deg; i <<= 1) {
ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
}
return ret.pre(deg);
}
FPS log(int deg = -1) {
assert((*this)[0] == mint(1));
if (deg == -1) deg = this->size();
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
FPS exp(int deg = -1) const {
assert((*this)[0] == mint(0));
const int n = this->size();
if (deg == -1) deg = n;
FPS ret({mint(1)});
for (int i = 1; i < deg; i <<= 1) {
ret = (ret * (pre(i << 1) + mint(1) - ret.log(i << 1))).pre(i << 1);
}
return ret.pre(deg);
}
FPS pow(int64_t k, int deg = -1) const {
const int n = this->size();
if (deg == -1) deg = n;
if (k == 0) {
FPS ret(deg);
if (deg) ret[0] = 1;
return ret;
}
for (int i = 0; i < n; i++) {
if ((*this)[i] != mint(0)) {
mint rev = mint(1) / (*this)[i];
FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);
ret *= (*this)[i].pow(k);
ret = (ret << (i * k)).pre(deg);
if ((int)ret.size() < deg) ret.resize(deg, mint(0));
return ret;
}
if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));
}
return FPS(deg, mint(0));
}
FPS sqrt(int deg = -1) const {
const int n = this->size();
if (deg == -1) deg = n;
if (n == 0) return FPS(deg, 0);
if ((*this)[0] == mint(0)) {
for (int i = 1; i < n; i++) {
if ((*this)[i] != mint(0)) {
if (i & 1) return {};
if (deg - i / 2 <= 0) break;
auto ret = (*this >> i).sqrt(deg - i / 2);
if (ret.empty()) return {};
ret = ret << (i / 2);
if ((int)ret.size() < deg) ret.resize(deg, mint(0));
return ret;
}
}
return FPS(deg, 0);
}
int64_t sqr = mod_sqrt((*this)[0].val(), mint::mod());
if (sqr == -1) return {};
assert(sqr * sqr % mint::mod() == (*this)[0].val());
FPS ret({mint(sqr)});
mint inv2 = mint(2).inv();
for (int i = 1; i < deg; i <<= 1) {
ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
}
return ret.pre(deg);
}
mint eval(mint x) const {
mint r = 0, w = 1;
for (auto& v : *this) r += w * v, w *= x;
return r;
}
};
template <typename mint>
FormalPowerSeries<mint> FPS_Product(vector<FormalPowerSeries<mint>> f) {
int n = (int)f.size();
if (n == 0) return {1};
function<FormalPowerSeries<mint>(int, int)> calc = [&](int l, int r) {
if (r - l == 1) return f[l];
int m = (l + r) / 2;
return calc(l, m) * calc(m, r);
};
return calc(0, n);
}
#line 3 "TaylorShift.cpp"
// f(x + a)
template <typename mint>
FormalPowerSeries<mint> TaylorShift(FormalPowerSeries<mint> f, mint a, Binomial<mint>& bin) {
int n = f.size();
for (int i = 0; i < n; i++) f[i] *= bin.fact[i];
f = f.rev();
FormalPowerSeries<mint> g(n, mint(1));
for (int i = 1; i < n; i++) g[i] = g[i - 1] * a * bin.inv[i];
f = (f * g).pre(n);
f = f.rev();
for (int i = 0; i < n; i++) f[i] *= bin.factinv[i];
return f;
}
#line 2 "Series.cpp"
template <typename mint>
FormalPowerSeries<mint> stirling_first(int n, Binomial<mint>& bin) {
if (n == 0) return FormalPowerSeries<mint>{1};
auto f = stirling_first(n >> 1, bin);
f *= TaylorShift(f, -mint(n >> 1), bin);
if (n & 1) f = (f << 1) - f * (n - 1); // multiply x-(n-1)
return f;
}
template <typename mint>
vector<mint> stirling_second(int n, Binomial<mint>& bin) {
vector<mint> f(n + 1), g(n + 1);
mint sgn = 1;
for (int i = 0; i <= n; i++) {
f[i] = mint(i).pow(n) * bin.factinv[i];
g[i] = sgn * bin.factinv[i];
sgn = -sgn;
}
auto h = atcoder::convolution(f, g);
h.resize(n + 1);
return h;
}
template <typename mint>
vector<mint> stirling_second_fixedK(int n, int k, Binomial<mint>& bin) {
using fps = FormalPowerSeries<mint>;
fps f(n + 1);
for (int i = 1; i <= n; i++) f[i] = bin.factinv[i];
f = f.pow(k, n + 1);
vector<mint> res(n - k + 1);
for (int i = k; i <= n; i++) res[i - k] = f[i] * bin.fact[i] * bin.factinv[k];
return res;
}
template <typename mint>
vector<mint> bernoulli(int n, Binomial<mint>& bin) {
// bin require n+1
assert((int)bin.factinv.size() >= n + 2);
using fps = FormalPowerSeries<mint>;
fps f(n + 1);
for (int i = 0; i <= n; i++) f[i] = bin.factinv[i + 1];
f = f.inv(n + 1);
for (int i = 1; i <= n; i++) f[i] *= bin.fact[i];
return f;
}
template <typename mint>
vector<mint> bell(int n, Binomial<mint>& bin) {
using fps = FormalPowerSeries<mint>;
fps f(n + 1);
for (int i = 1; i <= n; i++) f[i] = bin.factinv[i];
f = f.exp(n + 1);
for (int i = 1; i <= n; i++) f[i] *= bin.fact[i];
return f;
}
template <typename mint>
vector<mint> partition(int n) {
FormalPowerSeries<mint> po(n + 1);
po[0] = 1;
for (int k = 1; k <= n; k++) {
if (1LL * k * (3 * k + 1) / 2 <= n) po[k * (3 * k + 1) / 2] += (k % 2 ? -1 : 1);
if (1LL * k * (3 * k - 1) / 2 <= n) po[k * (3 * k - 1) / 2] += (k % 2 ? -1 : 1);
}
return po.inv();
}
#line 3 "test/Series/StirlingFirst.test.cpp"
void solve() {
using mint = atcoder::modint998244353;
int n;
cin >> n;
Binomial<mint> bin(n);
auto f = stirling_first(n, bin);
for (auto x : f) cout << x.val() << " ";
cout << endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
solve();
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 0_00 |
![]() |
5 ms | 4 MB |
g++ | 1_00 |
![]() |
4 ms | 4 MB |
g++ | 262143_00 |
![]() |
96 ms | 12 MB |
g++ | 262144_00 |
![]() |
159 ms | 14 MB |
g++ | 2_00 |
![]() |
5 ms | 4 MB |
g++ | 491519_00 |
![]() |
193 ms | 21 MB |
g++ | 499999_00 |
![]() |
184 ms | 21 MB |
g++ | 500000_00 |
![]() |
179 ms | 19 MB |
g++ | 5000_00 |
![]() |
7 ms | 4 MB |
g++ | example_00 |
![]() |
4 ms | 4 MB |
clang++ | 0_00 |
![]() |
5 ms | 4 MB |
clang++ | 1_00 |
![]() |
4 ms | 4 MB |
clang++ | 262143_00 |
![]() |
93 ms | 13 MB |
clang++ | 262144_00 |
![]() |
161 ms | 14 MB |
clang++ | 2_00 |
![]() |
5 ms | 4 MB |
clang++ | 491519_00 |
![]() |
187 ms | 20 MB |
clang++ | 499999_00 |
![]() |
196 ms | 21 MB |
clang++ | 500000_00 |
![]() |
192 ms | 19 MB |
clang++ | 5000_00 |
![]() |
7 ms | 4 MB |
clang++ | example_00 |
![]() |
4 ms | 4 MB |