This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "setfunc/subset_convolution.hpp"
#pragma once #include "setfunc/ranked_zeta.hpp" template <typename T, int LIM = 20> vc<T> subset_convolution_square(const vc<T>& A) { auto RA = ranked_zeta<T, LIM>(A); int n = topbit(len(RA)); FOR(s, len(RA)) { auto& f = RA[s]; FOR_R(d, n + 1) { T x = 0; FOR(i, d + 1) x += f[i] * f[d - i]; f[d] = x; } } return ranked_mobius<T, LIM>(RA); } template <typename T, int LIM = 20> vc<T> subset_convolution(const vc<T>& A, const vc<T>& B) { if (A == B) return subset_convolution_square(A); auto RA = ranked_zeta<T, LIM>(A); auto RB = ranked_zeta<T, LIM>(B); int n = topbit(len(RA)); FOR(s, len(RA)) { auto &f = RA[s], &g = RB[s]; FOR_R(d, n + 1) { T x = 0; FOR(i, d + 1) x += f[i] * g[d - i]; f[d] = x; } } return ranked_mobius<T, LIM>(RA); }
#line 2 "setfunc/subset_convolution.hpp" #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 4 "setfunc/subset_convolution.hpp" template <typename T, int LIM = 20> vc<T> subset_convolution_square(const vc<T>& A) { auto RA = ranked_zeta<T, LIM>(A); int n = topbit(len(RA)); FOR(s, len(RA)) { auto& f = RA[s]; FOR_R(d, n + 1) { T x = 0; FOR(i, d + 1) x += f[i] * f[d - i]; f[d] = x; } } return ranked_mobius<T, LIM>(RA); } template <typename T, int LIM = 20> vc<T> subset_convolution(const vc<T>& A, const vc<T>& B) { if (A == B) return subset_convolution_square(A); auto RA = ranked_zeta<T, LIM>(A); auto RB = ranked_zeta<T, LIM>(B); int n = topbit(len(RA)); FOR(s, len(RA)) { auto &f = RA[s], &g = RB[s]; FOR_R(d, n + 1) { T x = 0; FOR(i, d + 1) x += f[i] * g[d - i]; f[d] = x; } } return ranked_mobius<T, LIM>(RA); }