This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution" #include <iostream> #include <atcoder/modint> #include "library/convolution/xor_convolution.hpp" using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } template <typename T> std::ostream& operator<<(std::ostream& out, const std::vector<T> &a) { int n = a.size(); for (int i = 0; i < n; ++i) { out << a[i]; if (i != n - 1) out << ' '; } return out; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> a(1 << n), b(1 << n); for (auto &v : a) std::cin >> v; for (auto &v : b) std::cin >> v; std::cout << suisen::xor_convolution<mint>(std::move(a), std::move(b)) << std::endl; return 0; }
#line 1 "test/src/convolution/xor_convolution/xor_convolution.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/bitwise_xor_convolution" #include <iostream> #include <atcoder/modint> #line 1 "library/convolution/xor_convolution.hpp" #line 1 "library/transform/walsh_hadamard.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/walsh_hadamard.hpp" namespace suisen::walsh_hadamard_transform { namespace internal { template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>> void unit_transform(T& x0, T& x1) { T y0 = x0, y1 = x1; x0 = add(y0, y1); // 1, 1 x1 = sub(y0, y1); // 1, -1 } } // namespace internal using kronecker_power_transform::kronecker_power_transform; template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>> void walsh_hadamard(std::vector<T>& a) { kronecker_power_transform<T, 2, internal::unit_transform<T, add, sub>>(a); } template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto div = default_operator::div<T>, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> void walsh_hadamard_inv(std::vector<T>& a) { walsh_hadamard<T, add, sub>(a); const T n{ a.size() }; for (auto& val : a) val = div(val, n); } template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto mul = default_operator::mul<T>, auto inv = default_operator::inv<T>, std::enable_if_t<std::negation_v<std::is_integral<T>>, std::nullptr_t> = nullptr> void walsh_hadamard_inv(std::vector<T>& a) { walsh_hadamard<T, add, sub>(a); const T n{ a.size() }; const T inv_n = inv(n); for (auto& val : a) val = mul(val, inv_n); } } // namespace suisen::walsh_hadamard_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/xor_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 div = default_operator::div<T>, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr > std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) { return convolution::transform_convolution< T, walsh_hadamard_transform::walsh_hadamard<T, add, sub>, walsh_hadamard_transform::walsh_hadamard_inv<T, add, sub, div>, mul >(std::move(a), std::move(b)); } template < typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto mul = default_operator::mul<T>, auto inv = default_operator::inv<T>, std::enable_if_t<std::negation_v<std::is_integral<T>>, std::nullptr_t> = nullptr > std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) { return convolution::transform_convolution< T, walsh_hadamard_transform::walsh_hadamard<T, add, sub>, walsh_hadamard_transform::walsh_hadamard_inv<T, add, sub, mul, inv>, mul >(std::move(a), std::move(b)); } } // namespace suisen #line 7 "test/src/convolution/xor_convolution/xor_convolution.test.cpp" using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } template <typename T> std::ostream& operator<<(std::ostream& out, const std::vector<T> &a) { int n = a.size(); for (int i = 0; i < n; ++i) { out << a[i]; if (i != n - 1) out << ' '; } return out; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<mint> a(1 << n), b(1 << n); for (auto &v : a) std::cin >> v; for (auto &v : b) std::cin >> v; std::cout << suisen::xor_convolution<mint>(std::move(a), std::move(b)) << std::endl; return 0; }