This documentation is automatically generated by online-judge-tools/verification-helper
#include "setfunc/sps_inv.hpp"
#include "setfunc/ranked_zeta.hpp"
template <typename mint, int LIM>
vc<mint> sps_inv(vc<mint>& dp) {
const int N = topbit(len(dp));
assert(len(dp) == (1 << N) && dp[0] == mint(1));
auto RA = ranked_zeta<mint, LIM>(dp);
array<mint, LIM + 1> g;
FOR(s, 1 << N) {
auto& f = RA[s];
g[0] = 1;
FOR(k, 1, N + 1) {
g[k] = 0;
FOR(i, k) g[k] -= g[i] * f[k - i];
}
RA[s] = g;
}
return ranked_mobius<mint, LIM>(RA);
}
#line 2 "setfunc/ranked_zeta.hpp"
template <typename T, int LIM>
vc<array<T, LIM + 1>> ranked_zeta(const vc<T>& f) {
int n = topbit(len(f));
assert(n <= LIM);
assert(len(f) == 1 << n);
vc<array<T, LIM + 1>> Rf(1 << n);
for (int s = 0; s < (1 << n); ++s) Rf[s][popcnt(s)] = f[s];
for (int i = 0; i < n; ++i) {
int w = 1 << i;
for (int p = 0; p < (1 << n); p += 2 * w) {
for (int s = p; s < p + w; ++s) {
int t = s | 1 << i;
for (int d = 0; d <= n; ++d) Rf[t][d] += Rf[s][d];
}
}
}
return Rf;
}
template <typename T, int LIM>
vc<T> ranked_mobius(vc<array<T, LIM + 1>>& Rf) {
int n = topbit(len(Rf));
assert(len(Rf) == 1 << n);
for (int i = 0; i < n; ++i) {
int w = 1 << i;
for (int p = 0; p < (1 << n); p += 2 * w) {
for (int s = p; s < p + w; ++s) {
int t = s | 1 << i;
for (int d = 0; d <= n; ++d) Rf[t][d] -= Rf[s][d];
}
}
}
vc<T> f(1 << n);
for (int s = 0; s < (1 << n); ++s) f[s] = Rf[s][popcnt(s)];
return f;
}
#line 2 "setfunc/sps_inv.hpp"
template <typename mint, int LIM>
vc<mint> sps_inv(vc<mint>& dp) {
const int N = topbit(len(dp));
assert(len(dp) == (1 << N) && dp[0] == mint(1));
auto RA = ranked_zeta<mint, LIM>(dp);
array<mint, LIM + 1> g;
FOR(s, 1 << N) {
auto& f = RA[s];
g[0] = 1;
FOR(k, 1, N + 1) {
g[k] = 0;
FOR(i, k) g[k] -= g[i] * f[k - i];
}
RA[s] = g;
}
return ranked_mobius<mint, LIM>(RA);
}