Felix's Library
This documentation is automatically generated by online-judge-tools/verification-helper
library/convolution/subset-convolution.hpp
- View this file on GitHub
- Last update: 2023-05-28 03:49:52+08:00
- Include:
#include "library/convolution/subset-convolution.hpp"
Depends on
library/misc/type-traits.hpp
Verified with
- test/convolution/subset-convolution/yosupo-Bitwise-And-Convolution.test.cpp
- test/convolution/subset-convolution/yosupo-Bitwise-Xor-Convolution.test.cpp
- test/convolution/subset-convolution/yosupo-Subset-Convolution.test.cpp
Code
#pragma once
#include <vector>
#include <algorithm>
#include <cassert>
#include "../misc/type-traits.hpp"
namespace felix {
template<class T, class F>
void fwht(std::vector<T>& a, F f) {
const int n = (int) a.size();
assert(__builtin_popcount(n) == 1);
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(a[j + k], a[i + j + k]);
}
}
}
}
template<class T>
void or_transform(std::vector<T>& a, bool inv) {
fwht(a, [&](T& x, T& y) { y += x * (inv ? -1 : +1); });
}
template<class T>
void and_transform(std::vector<T>& a, bool inv) {
fwht(a, [&](T& x, T& y) { x += y * (inv ? -1 : +1); });
}
template<class T>
void xor_transform(std::vector<T>& a, bool inv) {
fwht(a, [](T& x, T& y) {
T z = x + y;
y = x - y;
x = z;
});
if(inv) {
if constexpr(internal::is_integral<T>::value) {
for(auto& x : a) {
x /= a.size();
}
} else {
T z = T(1) / T(a.size());
for(auto& x : a) {
x *= z;
}
}
}
}
template<class T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
or_transform(a, false);
or_transform(b, false);
for(int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
or_transform(a, true);
return a;
}
template<class T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
and_transform(a, false);
and_transform(b, false);
for(int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
and_transform(a, true);
return a;
}
template<class T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
xor_transform(a, false);
xor_transform(b, false);
for (int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
xor_transform(a, true);
return a;
}
template<class T>
std::vector<T> subset_convolution(const std::vector<T>& f, const std::vector<T>& g) {
assert(f.size() == g.size());
const int n = (int) f.size();
assert(__builtin_popcount(n) == 1);
const int lg = std::__lg(n);
std::vector<std::vector<T>> fhat(lg + 1, std::vector<T>(n)), ghat(fhat), h(fhat);
for(int mask = 0; mask < n; mask++) {
fhat[__builtin_popcount(mask)][mask] = f[mask];
ghat[__builtin_popcount(mask)][mask] = g[mask];
}
for(int i = 0; i <= lg; ++i) {
or_transform(fhat[i], false);
or_transform(ghat[i], false);
}
for(int mask = 0; mask < n; mask++) {
for(int i = 0; i <= lg; ++i) {
for(int j = 0; j <= i; ++j) {
h[i][mask] += fhat[j][mask] * ghat[i - j][mask];
}
}
}
for(int i = 0; i <= lg; ++i) {
or_transform(h[i], true);
}
std::vector<T> result(n);
for(int mask = 0; mask < n; mask++) {
result[mask] = h[__builtin_popcount(mask)][mask];
}
return result;
}
} // namespace felix#line 2 "library/convolution/subset-convolution.hpp"
#include <vector>
#include <algorithm>
#include <cassert>
#line 3 "library/misc/type-traits.hpp"
#include <numeric>
#include <type_traits>
namespace felix {
namespace internal {
#ifndef _MSC_VER
template<class T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type;
template<class T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template<class T> using is_integral = typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_signed_int = typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
#else
template<class T> using is_integral = typename std::is_integral<T>;
template<class T> using is_signed_int = typename std::conditional<is_integral<T>::value && std::is_signed<T>::value, std::true_type, std::false_type>::type;
template<class T> using is_unsigned_int = typename std::conditional<is_integral<T>::value && std::is_unsigned<T>::value, std::true_type, std::false_type>::type;
template<class T> using to_unsigned = typename std::conditional<is_signed_int<T>::value, std::make_unsigned<T>, std::common_type<T>>::type;
#endif
template<class T> using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template<class T> using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template<class T> using to_unsigned_t = typename to_unsigned<T>::type;
template<class T> struct safely_multipliable {};
template<> struct safely_multipliable<short> { using type = int; };
template<> struct safely_multipliable<unsigned short> { using type = unsigned int; };
template<> struct safely_multipliable<int> { using type = long long; };
template<> struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template<> struct safely_multipliable<long long> { using type = __int128; };
template<> struct safely_multipliable<unsigned long long> { using type = __uint128_t; };
template<class T> using safely_multipliable_t = typename safely_multipliable<T>::type;
} // namespace internal
} // namespace felix
#line 6 "library/convolution/subset-convolution.hpp"
namespace felix {
template<class T, class F>
void fwht(std::vector<T>& a, F f) {
const int n = (int) a.size();
assert(__builtin_popcount(n) == 1);
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(a[j + k], a[i + j + k]);
}
}
}
}
template<class T>
void or_transform(std::vector<T>& a, bool inv) {
fwht(a, [&](T& x, T& y) { y += x * (inv ? -1 : +1); });
}
template<class T>
void and_transform(std::vector<T>& a, bool inv) {
fwht(a, [&](T& x, T& y) { x += y * (inv ? -1 : +1); });
}
template<class T>
void xor_transform(std::vector<T>& a, bool inv) {
fwht(a, [](T& x, T& y) {
T z = x + y;
y = x - y;
x = z;
});
if(inv) {
if constexpr(internal::is_integral<T>::value) {
for(auto& x : a) {
x /= a.size();
}
} else {
T z = T(1) / T(a.size());
for(auto& x : a) {
x *= z;
}
}
}
}
template<class T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
or_transform(a, false);
or_transform(b, false);
for(int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
or_transform(a, true);
return a;
}
template<class T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
and_transform(a, false);
and_transform(b, false);
for(int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
and_transform(a, true);
return a;
}
template<class T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
assert(a.size() == b.size());
xor_transform(a, false);
xor_transform(b, false);
for (int i = 0; i < (int) a.size(); i++) {
a[i] *= b[i];
}
xor_transform(a, true);
return a;
}
template<class T>
std::vector<T> subset_convolution(const std::vector<T>& f, const std::vector<T>& g) {
assert(f.size() == g.size());
const int n = (int) f.size();
assert(__builtin_popcount(n) == 1);
const int lg = std::__lg(n);
std::vector<std::vector<T>> fhat(lg + 1, std::vector<T>(n)), ghat(fhat), h(fhat);
for(int mask = 0; mask < n; mask++) {
fhat[__builtin_popcount(mask)][mask] = f[mask];
ghat[__builtin_popcount(mask)][mask] = g[mask];
}
for(int i = 0; i <= lg; ++i) {
or_transform(fhat[i], false);
or_transform(ghat[i], false);
}
for(int mask = 0; mask < n; mask++) {
for(int i = 0; i <= lg; ++i) {
for(int j = 0; j <= i; ++j) {
h[i][mask] += fhat[j][mask] * ghat[i - j][mask];
}
}
}
for(int i = 0; i <= lg; ++i) {
or_transform(h[i], true);
}
std::vector<T> result(n);
for(int mask = 0; mask < n; mask++) {
result[mask] = h[__builtin_popcount(mask)][mask];
}
return result;
}
} // namespace felix