This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc253/tasks/abc253_Ex" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #include "library/util/subset_iterator.hpp" #include "library/linear_algebra/count_spanning_trees.hpp" #include "library/math/factorial.hpp" #include "library/math/set_power_series.hpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::pair<int, int>> edges(m); for (auto& [u, v] : edges) { std::cin >> u >> v; --u, --v; } suisen::FPSNaive<mint>::set_max_size(n + 1); suisen::SetPowerSeries<suisen::FPSNaive<mint>> f(n, suisen::FPSNaive<mint>(n)); for (int s = 1; s < 1 << n; ++s) { std::vector<int> ids(n, -1); int id = 0; for (int i : suisen::all_setbit(s)) ids[i] = id++; std::vector<std::pair<int, int>> Es; for (const auto& [u, v] : edges) if (ids[u] >= 0 and ids[v] >= 0) { Es.emplace_back(ids[u], ids[v]); } f[s] = { 0, suisen::count_spanning_trees<mint>(id, Es) }; } suisen::factorial<mint> fac(n); auto g = f.exp().back(); for (int k = 1; k < n; ++k) { std::cout << (fac.fac(k) * g[n - k] / mint(m).pow(k)).val() << std::endl; } return 0; }
#line 1 "test/src/math/set_power_series/abc253_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc253/tasks/abc253_Ex" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #line 1 "library/util/subset_iterator.hpp" #ifdef _MSC_VER # include <intrin.h> #else # include <x86intrin.h> #endif #include <cassert> #include <cstdint> #line 13 "library/util/subset_iterator.hpp" #include <limits> namespace suisen { template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> struct all_subset { struct all_subset_iter { const T s; T t; constexpr all_subset_iter(T s) : s(s), t(s + 1) {} constexpr auto operator*() const { return t; } constexpr auto operator++() {} constexpr auto operator!=(std::nullptr_t) { return t ? (--t &= s, true) : false; } }; T s; constexpr all_subset(T s) : s(s) {} constexpr auto begin() { return all_subset_iter(s); } constexpr auto end() { return nullptr; } }; // iterator over T s.t. T is subset of S and |T| = k struct all_subset_k { struct all_subset_k_iter { const uint32_t n, k, s; uint32_t t; __attribute__((target("avx2"))) all_subset_k_iter(uint32_t s, uint32_t k) : n(uint32_t(1) << _mm_popcnt_u32(s)), k(k), s(s), t((uint32_t(1) << k) - 1) {} __attribute__((target("bmi2"))) auto operator*() const { return _pdep_u32(t, s); } __attribute__((target("bmi"))) auto operator++() { if (k == 0) { t = std::numeric_limits<uint32_t>::max(); } else { uint32_t y = t + _blsi_u32(t); // t + (-t & t) t = y | ((y ^ t) >> _tzcnt_u32(t << 2)); } } auto operator!=(std::nullptr_t) const { return t < n; } }; uint32_t s, k; all_subset_k(uint32_t s, uint32_t k) : s(s), k(k) { assert(s != std::numeric_limits<uint32_t>::max()); } static all_subset_k nCk(uint32_t n, uint32_t k) { return all_subset_k((uint32_t(1) << n) - 1, k); } auto begin() { return all_subset_k_iter(s, k); } auto end() { return nullptr; } }; struct all_subset_k_64 { struct all_subset_k_iter_64 { const uint64_t n, s; const uint32_t k; uint64_t t; __attribute__((target("avx2"))) all_subset_k_iter_64(uint64_t s, uint32_t k) : n(uint64_t(1) << _mm_popcnt_u64(s)), s(s), k(k), t((uint64_t(1) << k) - 1) {} __attribute__((target("bmi2"))) auto operator*() const { return _pdep_u64(t, s); } __attribute__((target("bmi"))) auto operator++() { if (k == 0) { t = std::numeric_limits<uint64_t>::max(); } else { uint64_t y = t + _blsi_u64(t); t = y | ((y ^ t) >> _tzcnt_u64(t << 2)); } } auto operator!=(std::nullptr_t) const { return t < n; } }; uint64_t s; uint32_t k; all_subset_k_64(uint64_t s, uint32_t k) : s(s), k(k) { assert(s != std::numeric_limits<uint64_t>::max()); } auto begin() { return all_subset_k_iter_64(s, k); } auto end() { return nullptr; } }; struct all_setbit { struct all_setbit_iter { uint32_t s; all_setbit_iter(uint32_t s) : s(s) {} __attribute__((target("bmi"))) auto operator*() { return _tzcnt_u32(s); } __attribute__((target("bmi"))) auto operator++() { s = __blsr_u32(s); } auto operator!=(std::nullptr_t) { return s; } }; uint32_t s; all_setbit(uint32_t s) : s(s) {} auto begin() { return all_setbit_iter(s); } auto end() { return nullptr; } }; struct all_setbit_64 { struct all_setbit_iter_64 { uint64_t s; all_setbit_iter_64(uint64_t s) : s(s) {} __attribute__((target("bmi"))) auto operator*() { return _tzcnt_u64(s); } __attribute__((target("bmi"))) auto operator++() { s = __blsr_u64(s); } auto operator!=(std::nullptr_t) { return s; } }; uint64_t s; all_setbit_64(uint64_t s) : s(s) {} auto begin() { return all_setbit_iter_64(s); } auto end() { return nullptr; } }; } // namespace suisen #line 1 "library/linear_algebra/count_spanning_trees.hpp" #line 1 "library/linear_algebra/matrix.hpp" #include <algorithm> #line 6 "library/linear_algebra/matrix.hpp" #include <optional> #include <vector> namespace suisen { template <typename T> struct Matrix { std::vector<std::vector<T>> dat; Matrix() = default; Matrix(int n) : Matrix(n, n) {} Matrix(int n, int m, T fill_value = T(0)) : dat(n, std::vector<T>(m, fill_value)) {} Matrix(const std::vector<std::vector<T>>& dat) : dat(dat) {} const std::vector<T>& operator[](int i) const { return dat[i]; } std::vector<T>& operator[](int i) { return dat[i]; } operator std::vector<std::vector<T>>() const { return dat; } friend bool operator==(const Matrix<T>& A, const Matrix<T>& B) { return A.dat == B.dat; } friend bool operator!=(const Matrix<T>& A, const Matrix<T>& B) { return A.dat != B.dat; } std::pair<int, int> shape() const { return dat.empty() ? std::make_pair<int, int>(0, 0) : std::make_pair<int, int>(dat.size(), dat[0].size()); } int row_size() const { return dat.size(); } int col_size() const { return dat.empty() ? 0 : dat[0].size(); } friend Matrix<T>& operator+=(Matrix<T>& A, const Matrix<T>& B) { assert(A.shape() == B.shape()); auto [n, m] = A.shape(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) A.dat[i][j] += B.dat[i][j]; return A; } friend Matrix<T>& operator-=(Matrix<T>& A, const Matrix<T>& B) { assert(A.shape() == B.shape()); auto [n, m] = A.shape(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) A.dat[i][j] -= B.dat[i][j]; return A; } friend Matrix<T>& operator*=(Matrix<T>& A, const Matrix<T>& B) { return A = A * B; } friend Matrix<T>& operator*=(Matrix<T>& A, const T& val) { for (auto& row : A.dat) for (auto& elm : row) elm *= val; return A; } friend Matrix<T>& operator/=(Matrix<T>& A, const T& val) { return A *= T(1) / val; } friend Matrix<T>& operator/=(Matrix<T>& A, const Matrix<T>& B) { return A *= B.inv(); } friend Matrix<T> operator+(Matrix<T> A, const Matrix<T>& B) { A += B; return A; } friend Matrix<T> operator-(Matrix<T> A, const Matrix<T>& B) { A -= B; return A; } friend Matrix<T> operator*(const Matrix<T>& A, const Matrix<T>& B) { assert(A.col_size() == B.row_size()); const int n = A.row_size(), m = A.col_size(), l = B.col_size(); if (std::min({ n, m, l }) <= 70) { // naive Matrix<T> C(n, l); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int k = 0; k < l; ++k) { C.dat[i][k] += A.dat[i][j] * B.dat[j][k]; } return C; } // strassen const int nl = 0, nm = n >> 1, nr = nm + nm; const int ml = 0, mm = m >> 1, mr = mm + mm; const int ll = 0, lm = l >> 1, lr = lm + lm; auto A00 = A.submatrix(nl, nm, ml, mm), A01 = A.submatrix(nl, nm, mm, mr); auto A10 = A.submatrix(nm, nr, ml, mm), A11 = A.submatrix(nm, nr, mm, mr); auto B00 = B.submatrix(ml, mm, ll, lm), B01 = B.submatrix(ml, mm, lm, lr); auto B10 = B.submatrix(mm, mr, ll, lm), B11 = B.submatrix(mm, mr, lm, lr); auto P0 = (A00 + A11) * (B00 + B11); auto P1 = (A10 + A11) * B00; auto P2 = A00 * (B01 - B11); auto P3 = A11 * (B10 - B00); auto P4 = (A00 + A01) * B11; auto P5 = (A10 - A00) * (B00 + B01); auto P6 = (A01 - A11) * (B10 + B11); Matrix<T> C(n, l); C.assign_submatrix(nl, ll, P0 + P3 - P4 + P6), C.assign_submatrix(nl, lm, P2 + P4); C.assign_submatrix(nm, ll, P1 + P3), C.assign_submatrix(nm, lm, P0 + P2 - P1 + P5); // fractions if (l != lr) { for (int i = 0; i < nr; ++i) for (int j = 0; j < mr; ++j) C.dat[i][lr] += A.dat[i][j] * B.dat[j][lr]; } if (m != mr) { for (int i = 0; i < nr; ++i) for (int k = 0; k < l; ++k) C.dat[i][k] += A.dat[i][mr] * B.dat[mr][k]; } if (n != nr) { for (int j = 0; j < m; ++j) for (int k = 0; k < l; ++k) C.dat[nr][k] += A.dat[nr][j] * B.dat[j][k]; } return C; } friend Matrix<T> operator*(const T& val, Matrix<T> A) { A *= val; return A; } friend Matrix<T> operator*(Matrix<T> A, const T& val) { A *= val; return A; } friend Matrix<T> operator/(const Matrix<T>& A, const Matrix<T>& B) { return A * B.inv(); } friend Matrix<T> operator/(Matrix<T> A, const T& val) { A /= val; return A; } friend Matrix<T> operator/(const T& val, const Matrix<T>& A) { return val * A.inv(); } friend std::vector<T> operator*(const Matrix<T>& A, const std::vector<T>& x) { const auto [n, m] = A.shape(); assert(m == int(x.size())); std::vector<T> b(n, T(0)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) b[i] += A.dat[i][j] * x[j]; return b; } static Matrix<T> e0(int n) { return Matrix<T>(n, Identity::ADD); } static Matrix<T> e1(int n) { return Matrix<T>(n, Identity::MUL); } Matrix<T> pow(long long b) const { assert_square(); assert(b >= 0); Matrix<T> res = e1(row_size()), p = *this; for (; b; b >>= 1) { if (b & 1) res *= p; p *= p; } return res; } Matrix<T> inv() const { return *safe_inv(); } std::optional<Matrix<T>> safe_inv() const { assert_square(); Matrix<T> A = *this; const int n = A.row_size(); for (int i = 0; i < n; ++i) { A[i].resize(2 * n, T{ 0 }); A[i][n + i] = T{ 1 }; } for (int i = 0; i < n; ++i) { for (int k = i; k < n; ++k) if (A[k][i] != T{ 0 }) { std::swap(A[i], A[k]); T c = T{ 1 } / A[i][i]; for (int j = i; j < 2 * n; ++j) A[i][j] *= c; break; } if (A[i][i] == T{ 0 }) return std::nullopt; for (int k = 0; k < n; ++k) if (k != i and A[k][i] != T{ 0 }) { T c = A[k][i]; for (int j = i; j < 2 * n; ++j) A[k][j] -= c * A[i][j]; } } for (auto& row : A.dat) row.erase(row.begin(), row.begin() + n); return A; } T det() const { assert_square(); Matrix<T> A = *this; bool sgn = false; const int n = A.row_size(); for (int j = 0; j < n; ++j) for (int i = j + 1; i < n; ++i) if (A[i][j] != T{ 0 }) { std::swap(A[j], A[i]); T q = A[i][j] / A[j][j]; for (int k = j; k < n; ++k) A[i][k] -= A[j][k] * q; sgn = not sgn; } T res = sgn ? T{ -1 } : T{ +1 }; for (int i = 0; i < n; ++i) res *= A[i][i]; return res; } T det_arbitrary_mod() const { assert_square(); Matrix<T> A = *this; bool sgn = false; const int n = A.row_size(); for (int j = 0; j < n; ++j) for (int i = j + 1; i < n; ++i) { for (; A[i][j].val(); sgn = not sgn) { std::swap(A[j], A[i]); T q = A[i][j].val() / A[j][j].val(); for (int k = j; k < n; ++k) A[i][k] -= A[j][k] * q; } } T res = sgn ? -1 : +1; for (int i = 0; i < n; ++i) res *= A[i][i]; return res; } void assert_square() const { assert(row_size() == col_size()); } Matrix<T> submatrix(int row_begin, int row_end, int col_begin, int col_end) const { Matrix<T> A(row_end - row_begin, col_end - col_begin); for (int i = row_begin; i < row_end; ++i) for (int j = col_begin; j < col_end; ++j) { A[i - row_begin][j - col_begin] = dat[i][j]; } return A; } void assign_submatrix(int row_begin, int col_begin, const Matrix<T>& A) { const int n = A.row_size(), m = A.col_size(); assert(row_begin + n <= row_size() and col_begin + m <= col_size()); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { dat[row_begin + i][col_begin + j] = A[i][j]; } } private: enum class Identity { ADD, MUL }; Matrix(int n, Identity ident) : Matrix<T>::Matrix(n) { if (ident == Identity::MUL) for (int i = 0; i < n; ++i) dat[i][i] = 1; } }; } // namespace suisen #line 5 "library/linear_algebra/count_spanning_trees.hpp" namespace suisen { template <typename T, typename Edge> T count_spanning_trees(const int n, const std::vector<Edge> &edges) { Matrix<T> A(n - 1); for (auto [u, v] : edges) if (u != v) { if (u > v) std::swap(u, v); ++A[u][u]; if (v != n - 1) ++A[v][v], --A[u][v], --A[v][u]; } return A.det(); } } // namespace suisen #line 1 "library/math/factorial.hpp" #line 6 "library/math/factorial.hpp" namespace suisen { template <typename T, typename U = T> struct factorial { factorial() = default; factorial(int n) { ensure(n); } static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } T fac(const int i) { ensure(i); return _fac[i]; } T operator()(int i) { return fac(i); } U fac_inv(const int i) { ensure(i); return _fac_inv[i]; } U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } template <typename ...Ds, std::enable_if_t<std::conjunction_v<std::is_integral<Ds>...>, std::nullptr_t> = nullptr> U polynom(const int n, const Ds& ...ds) { if (n < 0) return 0; ensure(n); int sumd = 0; U res = _fac[n]; for (int d : { ds... }) { if (d < 0 or d > n) return 0; sumd += d; res *= _fac_inv[d]; } if (sumd > n) return 0; res *= _fac_inv[n - sumd]; return res; } U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector<T> _fac; static std::vector<U> _fac_inv; }; template <typename T, typename U> std::vector<T> factorial<T, U>::_fac{ 1 }; template <typename T, typename U> std::vector<U> factorial<T, U>::_fac_inv{ 1 }; } // namespace suisen #line 1 "library/math/set_power_series.hpp" #line 1 "library/convolution/subset_convolution.hpp" #line 1 "library/polynomial/fps_naive.hpp" #line 5 "library/polynomial/fps_naive.hpp" #include <cmath> #line 7 "library/polynomial/fps_naive.hpp" #include <type_traits> #line 9 "library/polynomial/fps_naive.hpp" #line 1 "library/type_traits/type_traits.hpp" #line 7 "library/type_traits/type_traits.hpp" namespace suisen { template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>; template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; }; template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; }; template <typename T> static constexpr int bitnum_v = bitnum<T>::value; template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; }; template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value; template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; }; template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type; template <typename T, typename = void> struct rec_value_type { using type = T; }; template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> { using type = typename rec_value_type<typename T::value_type>::type; }; template <typename T> using rec_value_type_t = typename rec_value_type<T>::type; template <typename T> class is_iterable { template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T> class is_writable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_writable_v = is_writable<T>::value; template <typename T> class is_readable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_readable_v = is_readable<T>::value; } // namespace suisen #line 11 "library/polynomial/fps_naive.hpp" #line 1 "library/math/modint_extension.hpp" #line 6 "library/math/modint_extension.hpp" /** * refernce: https://37zigen.com/tonelli-shanks-algorithm/ * calculates x s.t. x^2 = a mod p in O((log p)^2). */ template <typename mint> std::optional<mint> safe_sqrt(mint a) { static int p = mint::mod(); if (a == 0) return std::make_optional(0); if (p == 2) return std::make_optional(a); if (a.pow((p - 1) / 2) != 1) return std::nullopt; mint b = 1; while (b.pow((p - 1) / 2) == 1) ++b; static int tlz = __builtin_ctz(p - 1), q = (p - 1) >> tlz; mint x = a.pow((q + 1) / 2); b = b.pow(q); for (int shift = 2; x * x != a; ++shift) { mint e = a.inv() * x * x; if (e.pow(1 << (tlz - shift)) != 1) x *= b; b *= b; } return std::make_optional(x); } /** * calculates x s.t. x^2 = a mod p in O((log p)^2). * if not exists, raises runtime error. */ template <typename mint> auto sqrt(mint a) -> decltype(mint::mod(), mint()) { return *safe_sqrt(a); } template <typename mint> auto log(mint a) -> decltype(mint::mod(), mint()) { assert(a == 1); return 0; } template <typename mint> auto exp(mint a) -> decltype(mint::mod(), mint()) { assert(a == 0); return 1; } template <typename mint, typename T> auto pow(mint a, T b) -> decltype(mint::mod(), mint()) { return a.pow(b); } template <typename mint> auto inv(mint a) -> decltype(mint::mod(), mint()) { return a.inv(); } #line 1 "library/math/inv_mods.hpp" #line 5 "library/math/inv_mods.hpp" namespace suisen { template <typename mint> class inv_mods { public: inv_mods() = default; inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = { 0, 1 }, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; template <typename mint> std::vector<mint> get_invs(const std::vector<mint>& vs) { const int n = vs.size(); mint p = 1; for (auto& e : vs) { p *= e; assert(e != 0); } mint ip = p.inv(); std::vector<mint> rp(n + 1); rp[n] = 1; for (int i = n - 1; i >= 0; --i) { rp[i] = rp[i + 1] * vs[i]; } std::vector<mint> res(n); for (int i = 0; i < n; ++i) { res[i] = ip * rp[i + 1]; ip *= vs[i]; } return res; } } #line 14 "library/polynomial/fps_naive.hpp" namespace suisen { template <typename T> struct FPSNaive : std::vector<T> { static inline int MAX_SIZE = std::numeric_limits<int>::max() / 2; using value_type = T; using element_type = rec_value_type_t<T>; using std::vector<value_type>::vector; FPSNaive(const std::initializer_list<value_type> l) : std::vector<value_type>::vector(l) {} FPSNaive(const std::vector<value_type>& v) : std::vector<value_type>::vector(v) {} static void set_max_size(int n) { FPSNaive<T>::MAX_SIZE = n; } const value_type operator[](int n) const { return n <= deg() ? unsafe_get(n) : value_type{ 0 }; } value_type& operator[](int n) { return ensure_deg(n), unsafe_get(n); } int size() const { return std::vector<value_type>::size(); } int deg() const { return size() - 1; } int normalize() { while (size() and this->back() == value_type{ 0 }) this->pop_back(); return deg(); } FPSNaive& cut_inplace(int n) { if (size() > n) this->resize(std::max(0, n)); return *this; } FPSNaive cut(int n) const { FPSNaive f = FPSNaive(*this).cut_inplace(n); return f; } FPSNaive operator+() const { return FPSNaive(*this); } FPSNaive operator-() const { FPSNaive f(*this); for (auto& e : f) e = -e; return f; } FPSNaive& operator++() { return ++(*this)[0], * this; } FPSNaive& operator--() { return --(*this)[0], * this; } FPSNaive& operator+=(const value_type x) { return (*this)[0] += x, *this; } FPSNaive& operator-=(const value_type x) { return (*this)[0] -= x, *this; } FPSNaive& operator+=(const FPSNaive& g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i); return *this; } FPSNaive& operator-=(const FPSNaive& g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i); return *this; } FPSNaive& operator*=(const FPSNaive& g) { return *this = *this * g; } FPSNaive& operator*=(const value_type x) { for (auto& e : *this) e *= x; return *this; } FPSNaive& operator/=(const FPSNaive& g) { return *this = *this / g; } FPSNaive& operator%=(const FPSNaive& g) { return *this = *this % g; } FPSNaive& operator<<=(const int shamt) { this->insert(this->begin(), shamt, value_type{ 0 }); return *this; } FPSNaive& operator>>=(const int shamt) { if (shamt > size()) this->clear(); else this->erase(this->begin(), this->begin() + shamt); return *this; } friend FPSNaive operator+(FPSNaive f, const FPSNaive& g) { f += g; return f; } friend FPSNaive operator+(FPSNaive f, const value_type& x) { f += x; return f; } friend FPSNaive operator-(FPSNaive f, const FPSNaive& g) { f -= g; return f; } friend FPSNaive operator-(FPSNaive f, const value_type& x) { f -= x; return f; } friend FPSNaive operator*(const FPSNaive& f, const FPSNaive& g) { if (f.empty() or g.empty()) return FPSNaive{}; const int n = f.size(), m = g.size(); FPSNaive h(std::min(MAX_SIZE, n + m - 1)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (i + j >= MAX_SIZE) break; h.unsafe_get(i + j) += f.unsafe_get(i) * g.unsafe_get(j); } return h; } friend FPSNaive operator*(FPSNaive f, const value_type& x) { f *= x; return f; } friend FPSNaive operator/(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).first); } friend FPSNaive operator%(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).second); } friend FPSNaive operator*(const value_type x, FPSNaive f) { f *= x; return f; } friend FPSNaive operator<<(FPSNaive f, const int shamt) { f <<= shamt; return f; } friend FPSNaive operator>>(FPSNaive f, const int shamt) { f >>= shamt; return f; } std::pair<FPSNaive, FPSNaive> div_mod(FPSNaive g) const { FPSNaive f = *this; const int fd = f.normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) return { FPSNaive{}, f }; if (gd == 0) return { f *= g.unsafe_get(0).inv(), FPSNaive{} }; const int k = f.deg() - gd; value_type head_inv = g.unsafe_get(gd).inv(); FPSNaive q(k + 1); for (int i = k; i >= 0; --i) { value_type div = f.unsafe_get(i + gd) * head_inv; q.unsafe_get(i) = div; for (int j = 0; j <= gd; ++j) f.unsafe_get(i + j) -= div * g.unsafe_get(j); } f.cut_inplace(gd); f.normalize(); return { q, f }; } friend bool operator==(const FPSNaive& f, const FPSNaive& g) { const int n = f.size(), m = g.size(); if (n < m) return g == f; for (int i = 0; i < m; ++i) if (f.unsafe_get(i) != g.unsafe_get(i)) return false; for (int i = m; i < n; ++i) if (f.unsafe_get(i) != 0) return false; return true; } friend bool operator!=(const FPSNaive& f, const FPSNaive& g) { return not (f == g); } FPSNaive mul(const FPSNaive& g, int n = -1) const { if (n < 0) n = size(); if (this->empty() or g.empty()) return FPSNaive{}; const int m = size(), k = g.size(); FPSNaive h(std::min(n, m + k - 1)); for (int i = 0; i < m; ++i) { for (int j = 0, jr = std::min(k, n - i); j < jr; ++j) { h.unsafe_get(i + j) += unsafe_get(i) * g.unsafe_get(j); } } return h; } FPSNaive diff() const { if (this->empty()) return {}; FPSNaive g(size() - 1); for (int i = 1; i <= deg(); ++i) g.unsafe_get(i - 1) = unsafe_get(i) * i; return g; } FPSNaive intg() const { const int n = size(); FPSNaive g(n + 1); for (int i = 0; i < n; ++i) g.unsafe_get(i + 1) = unsafe_get(i) * invs[i + 1]; if (g.deg() > MAX_SIZE) g.cut_inplace(MAX_SIZE); return g; } FPSNaive inv(int n = -1) const { if (n < 0) n = size(); FPSNaive g(n); const value_type inv_f0 = ::inv(unsafe_get(0)); g.unsafe_get(0) = inv_f0; for (int i = 1; i < n; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) -= g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= inv_f0; } return g; } FPSNaive exp(int n = -1) const { if (n < 0) n = size(); assert(unsafe_get(0) == value_type{ 0 }); FPSNaive g(n); g.unsafe_get(0) = value_type{ 1 }; for (int i = 1; i < n; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) += j * g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= invs[i]; } return g; } FPSNaive log(int n = -1) const { if (n < 0) n = size(); assert(unsafe_get(0) == value_type{ 1 }); FPSNaive g(n); g.unsafe_get(0) = value_type{ 0 }; for (int i = 1; i < n; ++i) { g.unsafe_get(i) = i * (*this)[i]; for (int j = 1; j < i; ++j) g.unsafe_get(i) -= (i - j) * g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= invs[i]; } return g; } FPSNaive pow(const long long k, int n = -1) const { if (n < 0) n = size(); if (k == 0) { FPSNaive res(n); res[0] = 1; return res; } int z = 0; while (z < size() and unsafe_get(z) == value_type{ 0 }) ++z; if (z == size() or z > (n - 1) / k) return FPSNaive(n, 0); const int m = n - z * k; FPSNaive g(m); const value_type inv_f0 = ::inv(unsafe_get(z)); g.unsafe_get(0) = unsafe_get(z).pow(k); for (int i = 1; i < m; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) += (element_type{ k } *j - (i - j)) * g.unsafe_get(i - j) * (*this)[z + j]; g.unsafe_get(i) *= inv_f0 * invs[i]; } g <<= z * k; return g; } std::optional<FPSNaive> safe_sqrt(int n = -1) const { if (n < 0) n = size(); int dl = 0; while (dl < size() and unsafe_get(dl) == value_type{ 0 }) ++dl; if (dl == size()) return FPSNaive(n, 0); if (dl & 1) return std::nullopt; const int m = n - dl / 2; FPSNaive g(m); auto opt_g0 = ::safe_sqrt((*this)[dl]); if (not opt_g0.has_value()) return std::nullopt; g.unsafe_get(0) = *opt_g0; value_type inv_2g0 = ::inv(2 * g.unsafe_get(0)); for (int i = 1; i < m; ++i) { g.unsafe_get(i) = (*this)[dl + i]; for (int j = 1; j < i; ++j) g.unsafe_get(i) -= g.unsafe_get(j) * g.unsafe_get(i - j); g.unsafe_get(i) *= inv_2g0; } g <<= dl / 2; return g; } FPSNaive sqrt(int n = -1) const { if (n < 0) n = size(); return *safe_sqrt(n); } value_type eval(value_type x) const { value_type y = 0; for (int i = size() - 1; i >= 0; --i) y = y * x + unsafe_get(i); return y; } private: static inline inv_mods<element_type> invs; void ensure_deg(int d) { if (deg() < d) this->resize(d + 1, value_type{ 0 }); } const value_type& unsafe_get(int i) const { return std::vector<value_type>::operator[](i); } value_type& unsafe_get(int i) { return std::vector<value_type>::operator[](i); } }; } // namespace suisen template <typename mint> suisen::FPSNaive<mint> sqrt(suisen::FPSNaive<mint> a) { return a.sqrt(); } template <typename mint> suisen::FPSNaive<mint> log(suisen::FPSNaive<mint> a) { return a.log(); } template <typename mint> suisen::FPSNaive<mint> exp(suisen::FPSNaive<mint> a) { return a.exp(); } template <typename mint, typename T> suisen::FPSNaive<mint> pow(suisen::FPSNaive<mint> a, T b) { return a.pow(b); } template <typename mint> suisen::FPSNaive<mint> inv(suisen::FPSNaive<mint> a) { return a.inv(); } #line 5 "library/convolution/subset_convolution.hpp" #line 1 "library/transform/subset.hpp" #line 1 "library/transform/kronecker_power.hpp" #line 5 "library/transform/kronecker_power.hpp" #include <utility> #line 7 "library/transform/kronecker_power.hpp" #line 1 "library/util/default_operator.hpp" namespace suisen { namespace default_operator { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; } template <typename T> auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(const T &x) -> decltype(-x) { return -x; } template <typename T> auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator namespace default_operator_noref { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(T x, T y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(T x, T y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(T x, T y) -> decltype(x * y) { return x * y; } template <typename T> auto div(T x, T y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(T x, T y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(T x) -> decltype(-x) { return -x; } template <typename T> auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator } // namespace suisen #line 9 "library/transform/kronecker_power.hpp" namespace suisen { namespace kronecker_power_transform { namespace internal { template <typename UnitTransform, typename ReferenceGetter, std::size_t... Seq> void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence<Seq...>) { transform(ref_getter(Seq)...); } } template <typename T, std::size_t D, auto unit_transform> void kronecker_power_transform(std::vector<T> &x) { const std::size_t n = x.size(); for (std::size_t block = 1; block < n; block *= D) { for (std::size_t l = 0; l < n; l += D * block) { for (std::size_t offset = l; offset < l + block; ++offset) { const auto ref_getter = [&](std::size_t i) -> T& { return x[offset + i * block]; }; internal::unit_transform(unit_transform, ref_getter, std::make_index_sequence<D>()); } } } } template <typename T, typename UnitTransform> void kronecker_power_transform(std::vector<T> &x, const std::size_t D, UnitTransform unit_transform) { const std::size_t n = x.size(); std::vector<T> work(D); for (std::size_t block = 1; block < n; block *= D) { for (std::size_t l = 0; l < n; l += D * block) { for (std::size_t offset = l; offset < l + block; ++offset) { for (std::size_t i = 0; i < D; ++i) work[i] = x[offset + i * block]; unit_transform(work); for (std::size_t i = 0; i < D; ++i) x[offset + i * block] = work[i]; } } } } template <typename T, auto e = default_operator::zero<T>, auto add = default_operator::add<T>, auto mul = default_operator::mul<T>> auto kronecker_power_transform(std::vector<T> &x, const std::vector<std::vector<T>> &A) -> decltype(e(), add(std::declval<T>(), std::declval<T>()), mul(std::declval<T>(), std::declval<T>()), void()) { const std::size_t D = A.size(); assert(D == A[0].size()); auto unit_transform = [&](std::vector<T> &x) { std::vector<T> y(D, e()); for (std::size_t i = 0; i < D; ++i) for (std::size_t j = 0; j < D; ++j) { y[i] = add(y[i], mul(A[i][j], x[j])); } x.swap(y); }; kronecker_power_transform<T>(x, D, unit_transform); } } } // namespace suisen #line 5 "library/transform/subset.hpp" namespace suisen::subset_transform { namespace internal { template <typename T, auto add = default_operator::add<T>> void zeta_unit_transform(T &x0, T &x1) { // 1, 0 x1 = add(x1, x0); // 1, 1 } template <typename T, auto sub = default_operator::sub<T>> void mobius_unit_transform(T &x0, T &x1) { // 1, 0 x1 = sub(x1, x0); // -1, 1 } } // namespace internal using kronecker_power_transform::kronecker_power_transform; template <typename T, auto add = default_operator::add<T>> void zeta(std::vector<T> &a) { kronecker_power_transform<T, 2, internal::zeta_unit_transform<T, add>>(a); } template <typename T, auto sub = default_operator::sub<T>> void mobius(std::vector<T> &a) { kronecker_power_transform<T, 2, internal::mobius_unit_transform<T, sub>>(a); } } // namespace suisen::subset_transform #line 7 "library/convolution/subset_convolution.hpp" namespace suisen { namespace ranked_subset_transform { template <typename T> using polynomial_t = FPSNaive<T>; namespace internal { template <typename T> std::vector<polynomial_t<T>> ranked(const std::vector<T>& a) { const int n = a.size(); assert((-n & n) == n); std::vector fs(n, polynomial_t<T>(__builtin_ctz(n) + 1, T{ 0 })); for (int i = 0; i < n; ++i) fs[i][__builtin_popcount(i)] = a[i]; return fs; } template <typename T> std::vector<T> deranked(const std::vector<polynomial_t<T>>& polys) { const int n = polys.size(); assert((-n & n) == n); std::vector<T> a(n); for (int i = 0; i < n; ++i) a[i] = polys[i][__builtin_popcount(i)]; return a; } } // suisen::ranked_subset_transform::internal template <typename T> std::vector<polynomial_t<T>> ranked_zeta(const std::vector<T>& a) { std::vector<polynomial_t<T>> ranked = internal::ranked<T>(a); subset_transform::zeta(ranked); return ranked; } template <typename T> std::vector<T> deranked_mobius(std::vector<polynomial_t<T>>& ranked) { subset_transform::mobius(ranked); return internal::deranked<T>(ranked); } } // suisen::ranked_subset_transform template <typename T> std::vector<T> subset_convolution(const std::vector<T>& a, const std::vector<T>& b) { const int n = a.size(); auto ra = ranked_subset_transform::ranked_zeta(a), rb = ranked_subset_transform::ranked_zeta(b); for (int i = 0; i < n; ++i) ra[i] = ra[i].mul(rb[i], ra[i].size()); return ranked_subset_transform::deranked_mobius(ra); } } // namespace suisen #line 5 "library/math/set_power_series.hpp" namespace suisen { template <typename T> struct SetPowerSeries: public std::vector<T> { using base_type = std::vector<T>; using value_type = typename base_type::value_type; using size_type = typename base_type::size_type; using polynomial_type = ranked_subset_transform::polynomial_t<value_type>; using base_type::vector; SetPowerSeries(): SetPowerSeries(0) {} SetPowerSeries(size_type n): SetPowerSeries(n, value_type{ 0 }) {} SetPowerSeries(size_type n, const value_type& val): SetPowerSeries(std::vector<value_type>(1 << n, val)) {} SetPowerSeries(const base_type& a): SetPowerSeries(base_type(a)) {} SetPowerSeries(base_type&& a): base_type(std::move(a)) { const int n = this->size(); assert(n == (-n & n)); } SetPowerSeries(std::initializer_list<value_type> l): SetPowerSeries(base_type(l)) {} static SetPowerSeries one(int n) { SetPowerSeries f(n, value_type{ 0 }); f[0] = value_type{ 1 }; return f; } void set_cardinality(int n) { this->resize(1 << n, value_type{ 0 }); } int cardinality() const { return __builtin_ctz(this->size()); } SetPowerSeries cut_lower(size_type p) const { return SetPowerSeries(this->begin(), this->begin() + p); } SetPowerSeries cut_upper(size_type p) const { return SetPowerSeries(this->begin() + p, this->begin() + p + p); } void concat(const SetPowerSeries& upper) { assert(this->size() == upper.size()); this->insert(this->end(), upper.begin(), upper.end()); } SetPowerSeries operator+() const { return *this; } SetPowerSeries operator-() const { SetPowerSeries res(*this); for (auto& e : res) e = -e; return res; } SetPowerSeries& operator+=(const SetPowerSeries& g) { for (size_type i = 0; i < g.size(); ++i) (*this)[i] += g[i]; return *this; } SetPowerSeries& operator-=(const SetPowerSeries& g) { for (size_type i = 0; i < g.size(); ++i) (*this)[i] -= g[i]; return *this; } SetPowerSeries& operator*=(const SetPowerSeries& g) { return *this = (zeta() *= g).mobius_inplace(); } SetPowerSeries& operator*=(const value_type& c) { for (auto& e : *this) e *= c; return *this; } SetPowerSeries& operator/=(const value_type& c) { value_type inv_c = ::inv(c); for (auto& e : *this) e *= inv_c; return *this; } friend SetPowerSeries operator+(SetPowerSeries f, const SetPowerSeries& g) { f += g; return f; } friend SetPowerSeries operator-(SetPowerSeries f, const SetPowerSeries& g) { f -= g; return f; } friend SetPowerSeries operator*(SetPowerSeries f, const SetPowerSeries& g) { f *= g; return f; } friend SetPowerSeries operator*(SetPowerSeries f, const value_type& c) { f *= c; return f; } friend SetPowerSeries operator*(const value_type& c, SetPowerSeries f) { f *= c; return f; } friend SetPowerSeries operator/(SetPowerSeries f, const value_type& c) { f /= c; return f; } SetPowerSeries inv() { return zeta().inv_inplace().mobius_inplace(); } SetPowerSeries sqrt() { return zeta().sqrt_inplace().mobius_inplace(); } SetPowerSeries exp() { return zeta().exp_inplace().mobius_inplace(); } SetPowerSeries log() { return zeta().log_inplace().mobius_inplace(); } SetPowerSeries pow(long long k) { return zeta().pow_inplace(k).mobius_inplace(); } static SetPowerSeries polynomial_composite(std::vector<T> f, const SetPowerSeries& g) { const int n = g.cardinality(); std::vector<ZetaSPS> dp(n + 1); for (int k = 0; k <= n; ++k) { T eval_g0 = 0; for (int j = f.size(); j-- > 0;) eval_g0 = eval_g0 * g[0] + f[j]; dp[k] = ZetaSPS({ eval_g0 }); if (const int l = f.size()) { for (int j = 1; j < l; ++j) f[j - 1] = f[j] * j; f.pop_back(); } } for (int m = 1; m <= n; ++m) { ZetaSPS hi_g = g.cut_upper(1 << (m - 1)).zeta(); for (int k = 0; k <= n - m; ++k) { dp[k].concat(dp[k + 1] * hi_g); } dp.pop_back(); } return dp[0].mobius_inplace(); } struct ZetaSPS: public std::vector<polynomial_type> { using base_type = std::vector<polynomial_type>; using base_type::vector; ZetaSPS() = default; ZetaSPS(const SetPowerSeries<value_type>& f): base_type::vector(ranked_subset_transform::ranked_zeta(f)), _d(f.cardinality()) {} ZetaSPS operator+() const { return *this; } ZetaSPS operator-() const { ZetaSPS res(*this); for (auto& f : res) f = -f; return res; } friend ZetaSPS operator+(ZetaSPS f, const ZetaSPS& g) { f += g; return f; } friend ZetaSPS operator-(ZetaSPS f, const ZetaSPS& g) { f -= g; return f; } friend ZetaSPS operator*(ZetaSPS f, const ZetaSPS& g) { f *= g; return f; } friend ZetaSPS operator*(ZetaSPS f, const value_type& c) { f *= c; return f; } friend ZetaSPS operator*(const value_type& c, ZetaSPS f) { f *= c; return f; } friend ZetaSPS operator/(ZetaSPS f, const value_type& c) { f /= c; return f; } ZetaSPS& operator+=(const ZetaSPS& rhs) { assert(_d == rhs._d); for (int i = 0; i < 1 << _d; ++i) (*this)[i] += rhs[i]; return *this; } ZetaSPS& operator-=(const ZetaSPS& rhs) { assert(_d == rhs._d); for (int i = 0; i < 1 << _d; ++i) (*this)[i] -= rhs[i]; return *this; } ZetaSPS& operator*=(value_type c) { for (auto& f : *this) f *= c; return *this; } ZetaSPS& operator/=(value_type c) { value_type inv_c = ::inv(c); for (auto& f : *this) f *= inv_c; return *this; } ZetaSPS& operator*=(const ZetaSPS& rhs) { assert(_d == rhs._d); for (size_type i = 0; i < size_type(1) << _d; ++i) (*this)[i] = (*this)[i].mul(rhs[i], _d + 1); return *this; } ZetaSPS inv() const { auto f = ZetaSPS(*this).inv_inplace(); return f; } ZetaSPS sqrt() const { auto f = ZetaSPS(*this).sqrt_inplace(); return f; } ZetaSPS exp() const { auto f = ZetaSPS(*this).exp_inplace(); return f; } ZetaSPS log() const { auto f = ZetaSPS(*this).log_inplace(); return f; } ZetaSPS pow(long long k) const { auto f = ZetaSPS(*this).pow_inplace(k); return f; } ZetaSPS& inv_inplace() { for (auto& f : *this) f = f.inv(_d + 1); return *this; } ZetaSPS& sqrt_inplace() { for (auto& f : *this) f = f.sqrt(_d + 1); return *this; } ZetaSPS& exp_inplace() { for (auto& f : *this) f = f.exp(_d + 1); return *this; } ZetaSPS& log_inplace() { for (auto& f : *this) f = f.log(_d + 1); return *this; } ZetaSPS& pow_inplace(long long k) { for (auto& f : *this) f = f.pow(k, _d + 1); return *this; } void concat(const ZetaSPS& rhs) { assert(_d == rhs._d); this->reserve(1 << (_d + 1)); for (size_type i = 0; i < size_type(1) << _d; ++i) { this->push_back((rhs[i] << 1) += (*this)[i]); } ++_d; } SetPowerSeries<value_type> mobius_inplace() { return ranked_subset_transform::deranked_mobius<value_type>(*this); } SetPowerSeries<value_type> mobius() const { auto rf = ZetaSPS(*this); return ranked_subset_transform::deranked_mobius<value_type>(rf); } private: int _d; }; ZetaSPS zeta() const { return ZetaSPS(*this); } }; } // namespace suisen #line 12 "test/src/math/set_power_series/abc253_h.test.cpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::pair<int, int>> edges(m); for (auto& [u, v] : edges) { std::cin >> u >> v; --u, --v; } suisen::FPSNaive<mint>::set_max_size(n + 1); suisen::SetPowerSeries<suisen::FPSNaive<mint>> f(n, suisen::FPSNaive<mint>(n)); for (int s = 1; s < 1 << n; ++s) { std::vector<int> ids(n, -1); int id = 0; for (int i : suisen::all_setbit(s)) ids[i] = id++; std::vector<std::pair<int, int>> Es; for (const auto& [u, v] : edges) if (ids[u] >= 0 and ids[v] >= 0) { Es.emplace_back(ids[u], ids[v]); } f[s] = { 0, suisen::count_spanning_trees<mint>(id, Es) }; } suisen::factorial<mint> fac(n); auto g = f.exp().back(); for (int k = 1; k < n; ++k) { std::cout << (fac.fac(k) * g[n - k] / mint(m).pow(k)).val() << std::endl; } return 0; }