cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/math/set_power_series/abc253_h.test.cpp
- View this file on GitHub
- Last update: 2024-01-30 20:57:42+09:00
- Problem: https://atcoder.jp/contests/abc253/tasks/abc253_Ex
Depends on
- Subset Convolution
(library/convolution/subset_convolution.hpp)
- 行列木定理による全域木の数え上げ
(library/linear_algebra/count_spanning_trees.hpp)
- Matrix
(library/linear_algebra/matrix.hpp)
- 階乗テーブル
(library/math/factorial.hpp)
- 逆元テーブル
(library/math/inv_mods.hpp)
- Modint Extension
(library/math/modint_extension.hpp)
- Set Power Series
(library/math/set_power_series.hpp)
- FFT-free な形式的べき級数
(library/polynomial/fps_naive.hpp)
- クロネッカー冪による線形変換 (仮称)
(library/transform/kronecker_power.hpp)
- 下位集合に対する高速ゼータ変換・高速メビウス変換
(library/transform/subset.hpp)
- Type Traits
(library/type_traits/type_traits.hpp)
- Default Operator
(library/util/default_operator.hpp)
- Subset Iterator
(library/util/subset_iterator.hpp)
Code
#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;
}