sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/stirling_number_of_the_second_kind" #include "../../math/modint.hpp" #include "../../math/stirling_second.hpp" #include <bits/stdc++.h> using namespace std; using ll = long long; using mint = Modint<998244353>; int main() { int N; cin >> N; auto ans = stirling_second_table<mint>(N); for (int i = 0; i <= N; ++i) { cout << ans[i] << (i < N ? " " : "\n"); } }
#line 1 "test/yosupo/stirling_number_of_the_second_kind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/stirling_number_of_the_second_kind" #line 2 "math/modint.hpp" #include <algorithm> #include <iostream> /** * @brief Mod int */ template <int m> class Modint { using mint = Modint; static_assert(m > 0, "Modulus must be positive"); public: static constexpr int mod() { return m; } constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {} constexpr int val() const { return x; } constexpr mint& operator+=(const mint& r) { if ((x += r.x) >= m) x -= m; return *this; } constexpr mint& operator-=(const mint& r) { if ((x += m - r.x) >= m) x -= m; return *this; } constexpr mint& operator*=(const mint& r) { x = static_cast<int>(1LL * x * r.x % m); return *this; } constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); } constexpr bool operator==(const mint& r) const { return x == r.x; } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint(-x); } constexpr friend mint operator+(const mint& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const mint& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const mint& l, const mint& r) { return mint(l) *= r; } constexpr friend mint operator/(const mint& l, const mint& r) { return mint(l) /= r; } constexpr mint inv() const { int a = x, b = m, u = 1, v = 0; while (b > 0) { int t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return mint(u); } constexpr mint pow(long long n) const { mint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend std::ostream& operator<<(std::ostream& os, const mint& r) { return os << r.x; } friend std::istream& operator>>(std::istream& is, mint& r) { long long t; is >> t; r = mint(t); return is; } private: int x; }; #line 2 "math/stirling_second.hpp" #include <vector> #line 2 "convolution/ntt.hpp" #include <bit> #line 4 "convolution/ntt.hpp" constexpr int get_primitive_root(int mod) { if (mod == 167772161) return 3; if (mod == 469762049) return 3; if (mod == 754974721) return 11; if (mod == 998244353) return 3; if (mod == 1224736769) return 3; } template <typename mint> void ntt(std::vector<mint>& a) { constexpr int mod = mint::mod(); constexpr mint primitive_root = get_primitive_root(mod); const int n = a.size(); for (int m = n; m > 1; m >>= 1) { mint omega = primitive_root.pow((mod - 1) / m); for (int s = 0; s < n / m; ++s) { mint w = 1; for (int i = 0; i < m / 2; ++i) { mint l = a[s * m + i]; mint r = a[s * m + i + m / 2]; a[s * m + i] = l + r; a[s * m + i + m / 2] = (l - r) * w; w *= omega; } } } } template <typename mint> void intt(std::vector<mint>& a) { constexpr int mod = mint::mod(); constexpr mint primitive_root = get_primitive_root(mod); const int n = a.size(); for (int m = 2; m <= n; m <<= 1) { mint omega = primitive_root.pow((mod - 1) / m).inv(); for (int s = 0; s < n / m; ++s) { mint w = 1; for (int i = 0; i < m / 2; ++i) { mint l = a[s * m + i]; mint r = a[s * m + i + m / 2] * w; a[s * m + i] = l + r; a[s * m + i + m / 2] = l - r; w *= omega; } } } } template <typename mint> std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) { const int size = a.size() + b.size() - 1; const int n = std::bit_ceil((unsigned int)size); a.resize(n); b.resize(n); ntt(a); ntt(b); for (int i = 0; i < n; ++i) a[i] *= b[i]; intt(a); a.resize(size); mint n_inv = mint(n).inv(); for (int i = 0; i < size; ++i) a[i] *= n_inv; return a; } #line 3 "math/combination.cpp" template <typename mint> class Combination { public: Combination() = default; Combination(int n) : fact_(n + 1), fact_inv_(n + 1) { fact_[0] = 1; for (int i = 1; i <= n; ++i) fact_[i] = fact_[i - 1] * i; fact_inv_[n]=fact_[n].inv(); for (int i = n; i > 0; --i) fact_inv_[i - 1] = fact_inv_[i] * i; } mint perm(int n, int k) const { if (k < 0 || n < k) return 0; return fact_[n] * fact_inv_[n - k]; } mint comb(int n, int k) const { if (k < 0 || n < k) return 0; return fact_[n] * fact_inv_[k] * fact_inv_[n - k]; } mint fact(int n) const { return fact_[n]; } mint fact_inv(int n) const { return fact_inv_[n]; } private: std::vector<mint> fact_, fact_inv_; }; template <typename T> T comb(long long n, int k) { if (k < 0 || n < k) return 0; T num = 1, den = 1; for (int i = 1; i <= k; ++i) { num = num * (n - i + 1); den = den * i; } return num / den; } #line 5 "math/stirling_second.hpp" template <typename T> std::vector<T> stirling_second_table(int n) { T f = 1; for (int i = 1; i <= n; ++i) f *= i; f = T(1) / f; std::vector<T> a(n + 1), b(n + 1); for (int i = n; i >= 0; --i) { a[i] = f * (i % 2 ? -1 : 1); b[i] = f * T(i).pow(n); f *= i; } auto c = convolution(a, b); return std::vector(c.begin(), c.begin() + n + 1); } template <typename T> T stirling_second(int n, int k) { Combination<T> comb(n); T res = 0; for (int i = 0; i <= k; ++i) { T tmp = comb.comb(k, i) * T(i).pow(n); if ((k - i) & 1) res -= tmp; else res += tmp; } res /= comb.fact(k); return res; } #line 6 "test/yosupo/stirling_number_of_the_second_kind.test.cpp" #include <bits/stdc++.h> using namespace std; using ll = long long; using mint = Modint<998244353>; int main() { int N; cin >> N; auto ans = stirling_second_table<mint>(N); for (int i = 0; i <= N; ++i) { cout << ans[i] << (i < N ? " " : "\n"); } }