This documentation is automatically generated by online-judge-tools/verification-helper
#include "library/convolution/or_convolution.hpp"
シグネチャ
template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto mul = default_operator::mul<T>>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b)
概要
長さ $N=2^L$ の列 $(A_0,A_1,\ldots,A_{N-1})$ および $(B_0,B_1,\ldots,B_{N-1})$ を添字 bitwise or で畳み込みます.即ち,長さ $N$ の列 $(C_0,C_1,\ldots,C_{N-1})$ であって,各 $k=0,\ldots,N-1$ に対して以下を満たす列を計算します.
\[C _ k = \sum _ { i \mid j = k } A _ i \cdot B _ j\]以下,この畳み込みを $C=A\ast B$ と表記します.
テンプレート引数
T
: 列の要素の型.add
: 二項演算 (加算).デフォルトでは operator+
が呼ばれるようになっています.sub
: 二項演算 (減算).デフォルトでは operator-
が呼ばれるようになっています.mul
: 二項演算 (乗算).デフォルトでは operator*
が呼ばれるようになっています.返り値
$A\ast B$
制約
時間計算量
$\Theta(N\log N)$,あるいは $\Theta(L\cdot 2^L)$
#ifndef SUISEN_OR_CONVOLUTION
#define SUISEN_OR_CONVOLUTION
#include "library/transform/subset.hpp"
#include "library/convolution/convolution.hpp"
namespace suisen {
template <
typename T,
auto add = default_operator::add<T>,
auto sub = default_operator::sub<T>,
auto mul = default_operator::mul<T>
>
auto or_convolution(std::vector<T> a, std::vector<T> b) {
return convolution::transform_convolution<
T,
subset_transform::zeta<T, add>,
subset_transform::mobius<T, sub>,
mul
>(std::move(a), std::move(b));
}
} // namespace suisen
#endif // SUISEN_OR_CONVOLUTION
#line 1 "library/convolution/or_convolution.hpp"
#line 1 "library/transform/subset.hpp"
#line 1 "library/transform/kronecker_power.hpp"
#include <cassert>
#include <utility>
#include <vector>
#line 1 "library/util/default_operator.hpp"
namespace suisen {
namespace default_operator {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(const T &x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
namespace default_operator_noref {
template <typename T>
auto zero() -> decltype(T { 0 }) { return T { 0 }; }
template <typename T>
auto one() -> decltype(T { 1 }) { return T { 1 }; }
template <typename T>
auto add(T x, T y) -> decltype(x + y) { return x + y; }
template <typename T>
auto sub(T x, T y) -> decltype(x - y) { return x - y; }
template <typename T>
auto mul(T x, T y) -> decltype(x * y) { return x * y; }
template <typename T>
auto div(T x, T y) -> decltype(x / y) { return x / y; }
template <typename T>
auto mod(T x, T y) -> decltype(x % y) { return x % y; }
template <typename T>
auto neg(T x) -> decltype(-x) { return -x; }
template <typename T>
auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; }
} // default_operator
} // namespace suisen
#line 9 "library/transform/kronecker_power.hpp"
namespace suisen {
namespace kronecker_power_transform {
namespace internal {
template <typename UnitTransform, typename ReferenceGetter, std::size_t... Seq>
void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence<Seq...>) {
transform(ref_getter(Seq)...);
}
}
template <typename T, std::size_t D, auto unit_transform>
void kronecker_power_transform(std::vector<T> &x) {
const std::size_t n = x.size();
for (std::size_t block = 1; block < n; block *= D) {
for (std::size_t l = 0; l < n; l += D * block) {
for (std::size_t offset = l; offset < l + block; ++offset) {
const auto ref_getter = [&](std::size_t i) -> T& { return x[offset + i * block]; };
internal::unit_transform(unit_transform, ref_getter, std::make_index_sequence<D>());
}
}
}
}
template <typename T, typename UnitTransform>
void kronecker_power_transform(std::vector<T> &x, const std::size_t D, UnitTransform unit_transform) {
const std::size_t n = x.size();
std::vector<T> work(D);
for (std::size_t block = 1; block < n; block *= D) {
for (std::size_t l = 0; l < n; l += D * block) {
for (std::size_t offset = l; offset < l + block; ++offset) {
for (std::size_t i = 0; i < D; ++i) work[i] = x[offset + i * block];
unit_transform(work);
for (std::size_t i = 0; i < D; ++i) x[offset + i * block] = work[i];
}
}
}
}
template <typename T, auto e = default_operator::zero<T>, auto add = default_operator::add<T>, auto mul = default_operator::mul<T>>
auto kronecker_power_transform(std::vector<T> &x, const std::vector<std::vector<T>> &A) -> decltype(e(), add(std::declval<T>(), std::declval<T>()), mul(std::declval<T>(), std::declval<T>()), void()) {
const std::size_t D = A.size();
assert(D == A[0].size());
auto unit_transform = [&](std::vector<T> &x) {
std::vector<T> y(D, e());
for (std::size_t i = 0; i < D; ++i) for (std::size_t j = 0; j < D; ++j) {
y[i] = add(y[i], mul(A[i][j], x[j]));
}
x.swap(y);
};
kronecker_power_transform<T>(x, D, unit_transform);
}
}
} // namespace suisen
#line 5 "library/transform/subset.hpp"
namespace suisen::subset_transform {
namespace internal {
template <typename T, auto add = default_operator::add<T>>
void zeta_unit_transform(T &x0, T &x1) {
// 1, 0
x1 = add(x1, x0); // 1, 1
}
template <typename T, auto sub = default_operator::sub<T>>
void mobius_unit_transform(T &x0, T &x1) {
// 1, 0
x1 = sub(x1, x0); // -1, 1
}
} // namespace internal
using kronecker_power_transform::kronecker_power_transform;
template <typename T, auto add = default_operator::add<T>>
void zeta(std::vector<T> &a) {
kronecker_power_transform<T, 2, internal::zeta_unit_transform<T, add>>(a);
}
template <typename T, auto sub = default_operator::sub<T>>
void mobius(std::vector<T> &a) {
kronecker_power_transform<T, 2, internal::mobius_unit_transform<T, sub>>(a);
}
} // namespace suisen::subset_transform
#line 1 "library/convolution/convolution.hpp"
#line 6 "library/convolution/convolution.hpp"
#line 8 "library/convolution/convolution.hpp"
namespace suisen {
namespace convolution {
template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) {
const std::size_t n = a.size(), m = b.size();
assert(n == m);
transform(a), transform(b);
for (std::size_t i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
inv_transform(a);
return a;
}
template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
std::vector<T> transform_convolution(std::vector<std::vector<T>> a) {
const std::size_t num = a.size();
assert(num);
const std::size_t n = a[0].size();
for (auto &v : a) {
assert(n == int(v.size()));
transform(v);
}
auto &res = a[0];
for (int i = 1; i < num; ++i) {
for (int j = 0; j < n; ++j) res[j] = mul(res[j], a[i][j]);
}
inv_transform(res);
return res;
}
}
} // namespace suisen
#line 6 "library/convolution/or_convolution.hpp"
namespace suisen {
template <
typename T,
auto add = default_operator::add<T>,
auto sub = default_operator::sub<T>,
auto mul = default_operator::mul<T>
>
auto or_convolution(std::vector<T> a, std::vector<T> b) {
return convolution::transform_convolution<
T,
subset_transform::zeta<T, add>,
subset_transform::mobius<T, sub>,
mul
>(std::move(a), std::move(b));
}
} // namespace suisen