C++ Library for Competitive Programming
#include "emthrm/math/convolution/or_convolution.hpp"
$C_k = \sum_{k = i \circ j} A_i B_j$ を求める。ただし $\circ$ は二項演算である。
添え字 xor での畳み込みには『高速ウォルシュ・アダマール変換 (fast Walsh-Hadamard transform)』を用いる。
$O(N\log{N})$
名前 | 戻り値 |
---|---|
template <typename T> std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);
|
$A, B$ に対する添え字 and での畳み込み |
名前 | 戻り値 |
---|---|
template <typename T> std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);
|
$A, B$ に対する添え字 or での畳み込み |
名前 | 戻り値 |
---|---|
template <typename T> std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b, const T id = 0);
|
$A, B$ に対する添え字 xor での畳み込み |
名前 | 戻り値 |
---|---|
template <typename T> std::vector<T> gcd_convolution(std::vector<T> a, std::vector<T> b);
|
$A, B$ に対する添え字 gcd での畳み込み |
名前 | 戻り値 |
---|---|
template <typename T> std::vector<T> lcm_convolution(std::vector<T> a, std::vector<T> b, const int n = -1);
|
$A, B$ に対する添え字 lcm での畳み込み |
高速ウォルシュ・アダマール変換
添え字 gcd での畳み込み
添え字 lcm での畳み込み
#ifndef EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#define EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#include <algorithm>
#include <vector>
#include "emthrm/math/convolution/fast_mobius_transform.hpp"
#include "emthrm/math/convolution/fast_zeta_transform.hpp"
namespace emthrm {
template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b,
const T id = 0) {
int n = std::max(a.size(), b.size());
a.resize(n, id);
a = fast_zeta_transform<false>(a, id);
b.resize(n, id);
b = fast_zeta_transform<false>(b, id);
n = a.size();
for (int i = 0; i < n; ++i) {
a[i] *= b[i];
}
return fast_mobius_transform<false>(a);
}
} // namespace emthrm
#endif // EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#line 1 "include/emthrm/math/convolution/or_convolution.hpp"
#include <algorithm>
#include <vector>
#line 1 "include/emthrm/math/convolution/fast_mobius_transform.hpp"
#include <bit>
#line 6 "include/emthrm/math/convolution/fast_mobius_transform.hpp"
namespace emthrm {
template <bool ADDS_SUPERSET, typename T>
std::vector<T> fast_mobius_transform(std::vector<T> a, const T id = 0) {
const int n = std::bit_ceil(a.size());
a.resize(n, id);
for (int i = 1; i < n; i <<= 1) {
for (int s = 0; s < n; ++s) {
if (s & i) continue;
if constexpr (ADDS_SUPERSET) {
a[s] -= a[s | i];
} else {
a[s | i] -= a[s];
}
}
}
return a;
}
} // namespace emthrm
#line 1 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
#line 5 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
#include <functional>
#line 7 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
namespace emthrm {
template <bool ADDS_SUPERSET, typename Ring, typename BinOp = std::plus<Ring>>
std::vector<Ring> fast_zeta_transform(
std::vector<Ring> a, const Ring ID = 0, const BinOp bin_op = BinOp()) {
const int n = std::bit_ceil(a.size());
a.resize(n, ID);
for (int i = 1; i < n; i <<= 1) {
for (int s = 0; s < n; ++s) {
if (s & i) continue;
if constexpr (ADDS_SUPERSET) {
a[s] = bin_op(a[s], a[s | i]);
} else {
a[s | i] = bin_op(a[s | i], a[s]);
}
}
}
return a;
}
} // namespace emthrm
#line 9 "include/emthrm/math/convolution/or_convolution.hpp"
namespace emthrm {
template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b,
const T id = 0) {
int n = std::max(a.size(), b.size());
a.resize(n, id);
a = fast_zeta_transform<false>(a, id);
b.resize(n, id);
b = fast_zeta_transform<false>(b, id);
n = a.size();
for (int i = 0; i < n; ++i) {
a[i] *= b[i];
}
return fast_mobius_transform<false>(a);
}
} // namespace emthrm