This documentation is automatically generated by online-judge-tools/verification-helper
#include "convolution/superset-zeta-moebius-transform.hpp"
可換な二項演算(大抵の場合、数の和) $\oplus$ があるとき、
サイズ$N$の集合 $S$について、$f(S)$が($2^N$のvector
で)与えられたときに、
$ g(S) = \bigoplus_{S \subseteq T} f(T) $ を求めたり(Zeta)、その逆変換を求めたり(Möbius)する。
添字AND畳み込みは、上位集合についてゼータ変換したあとに各点積を取ってメビウス変換すると求められたりする。
Scrapboxを見るといっぱい資料がある。
ゼータもメビウスも
#ifndef HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP
#define HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP
#include <vector>
template <class T, T (*op)(T, T) >
std::vector<T> superset_zeta_transform(const std::vector<T>& f) {
int n = 0; while ((1 << n) < (int)f.size()) n++;
assert((int)f.size() == (1 << n)); // f.size() should be power of 2.
std::vector<T> F = f;
for (int k = 0; k < n; k++) {
for (int s = 0; s < 1 << n; s++) {
if (!((s >> k) & 1)) F[s] = op(F[s], F[s ^ (1 << k)]);
}
}
return F;
}
template <class T, T (*invop)(T, T) >
std::vector<T> superset_moebius_transform(const std::vector<T>& f) {
int n = 0; while ((1 << n) < (int)f.size()) n++;
assert((int)f.size() == (1 << n)); // f.size() should be power of 2.
std::vector<T> F = f;
for (int k = 0; k < n; k++) {
for (int s = 0; s < 1 << n; s++) {
if (!((s >> k) & 1)) F[s] = invop(F[s], F[s ^ (1 << k)]);
}
}
return F;
}
#endif // HARUILIB_CONVOLUTION_SUPERSET_ZETA_MOEBIUS_TRANSFORM_HPP
#line 1 "convolution/superset-zeta-moebius-transform.hpp"
#include <vector>
template <class T, T (*op)(T, T) >
std::vector<T> superset_zeta_transform(const std::vector<T>& f) {
int n = 0; while ((1 << n) < (int)f.size()) n++;
assert((int)f.size() == (1 << n)); // f.size() should be power of 2.
std::vector<T> F = f;
for (int k = 0; k < n; k++) {
for (int s = 0; s < 1 << n; s++) {
if (!((s >> k) & 1)) F[s] = op(F[s], F[s ^ (1 << k)]);
}
}
return F;
}
template <class T, T (*invop)(T, T) >
std::vector<T> superset_moebius_transform(const std::vector<T>& f) {
int n = 0; while ((1 << n) < (int)f.size()) n++;
assert((int)f.size() == (1 << n)); // f.size() should be power of 2.
std::vector<T> F = f;
for (int k = 0; k < n; k++) {
for (int s = 0; s < 1 << n; s++) {
if (!((s >> k) & 1)) F[s] = invop(F[s], F[s ^ (1 << k)]);
}
}
return F;
}