This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/bitwise_and_convolution.hpp"
bitwise_and_convolution(a, b)
: $c_k = \displaystyle \sum_{i\&j=k}a_ib_j$ となる数列 c
を求める。#pragma once
#include "zeta_mobius_transform.hpp"
template <typename mint>
std::vector<mint> bitwise_and_convolution(std::vector<mint> a,
std::vector<mint> b) {
superset_zeta(a);
superset_zeta(b);
for (int i = 0; i < int(a.size()); i++) {
a[i] *= b[i];
}
superset_mobius(a);
return a;
}
#line 2 "math/zeta_mobius_transform.hpp"
#include <cassert>
#include <vector>
template <typename mint>
void superset_zeta(std::vector<mint>& f) {
int n = f.size();
assert((n & -n) == n);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j++) {
if ((j & i) == 0) {
f[j] += f[j | i];
}
}
}
}
template <typename mint>
void superset_mobius(std::vector<mint>& f) {
int n = f.size();
assert((n & -n) == n);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j++) {
if ((j & i) == 0) {
f[j] -= f[j | i];
}
}
}
}
template <typename mint>
void subset_zeta(std::vector<mint>& f) {
int n = f.size();
assert((n & -n) == n);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j++) {
if ((j & i) == 0) {
f[j | i] += f[j];
}
}
}
}
template <typename mint>
void subset_mobius(std::vector<mint>& f) {
int n = f.size();
assert((n & -n) == n);
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j++) {
if ((j & i) == 0) {
f[j | i] -= f[j];
}
}
}
}
#line 3 "math/bitwise_and_convolution.hpp"
template <typename mint>
std::vector<mint> bitwise_and_convolution(std::vector<mint> a,
std::vector<mint> b) {
superset_zeta(a);
superset_zeta(b);
for (int i = 0; i < int(a.size()); i++) {
a[i] *= b[i];
}
superset_mobius(a);
return a;
}