This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/fft/bitwise-or-convolution.hpp"
#include "subset-zeta-moebius-transform.hpp"
/**
* @brief Bitwise Or Convolution (Bitwise-OR畳み込み)
*/
template <typename T>
vector<T> bitwise_or_convolution(vector<T> f, vector<T> g) {
const int n = (int)f.size();
assert(f.size() == g.size());
assert((n & (n - 1)) == 0);
subset_zeta_transform(f);
subset_zeta_transform(g);
for (int i = 0; i < n; i++) f[i] *= g[i];
subset_moebius_transform(f);
return f;
}
#line 1 "math/fft/subset-zeta-moebius-transform.hpp"
/**
* @brief Subset Zeta/Moebius Transform (下位集合のゼータ/メビウス変換)
*/
template <typename T>
void subset_zeta_transform(vector<T> &f) {
const int n = (int)f.size();
assert((n & (n - 1)) == 0);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j += i << 1) {
for (int k = 0; k < i; k++) {
f[j + k + i] += f[j + k];
}
}
}
}
template <typename T>
void subset_moebius_transform(vector<T> &f) {
const int n = (int)f.size();
assert((n & (n - 1)) == 0);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j += i << 1) {
for (int k = 0; k < i; k++) {
f[j + k + i] -= f[j + k];
}
}
}
}
#line 2 "math/fft/bitwise-or-convolution.hpp"
/**
* @brief Bitwise Or Convolution (Bitwise-OR畳み込み)
*/
template <typename T>
vector<T> bitwise_or_convolution(vector<T> f, vector<T> g) {
const int n = (int)f.size();
assert(f.size() == g.size());
assert((n & (n - 1)) == 0);
subset_zeta_transform(f);
subset_zeta_transform(g);
for (int i = 0; i < n; i++) f[i] *= g[i];
subset_moebius_transform(f);
return f;
}