This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution" #include "../../math/bitwise_or_convolution.hpp" #include <atcoder/modint> #include <iostream> using mint = atcoder::modint998244353; int main() { int n; std::cin >> n; int mask = (1 << n) - 1; std::vector<mint> a(1 << n), b(1 << n); for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; a[i ^ mask] = mint::raw(x); } for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; b[i ^ mask] = mint::raw(x); } std::vector<mint> c = bitwise_or_convolution(a, b); for (int i = 0; i < (1 << n); i++) { std::cout << c[i ^ mask].val() << " \n"[i == (1 << n) - 1]; } }
#line 1 "test/library-checker/bitwise_or_convolution.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution" #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_or_convolution.hpp" template <typename mint> std::vector<mint> bitwise_or_convolution(std::vector<mint> a, std::vector<mint> b) { subset_zeta(a); subset_zeta(b); for (int i = 0; i < int(a.size()); i++) { a[i] *= b[i]; } subset_mobius(a); return a; } #line 3 "test/library-checker/bitwise_or_convolution.test.cpp" #include <atcoder/modint> #include <iostream> using mint = atcoder::modint998244353; int main() { int n; std::cin >> n; int mask = (1 << n) - 1; std::vector<mint> a(1 << n), b(1 << n); for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; a[i ^ mask] = mint::raw(x); } for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; b[i ^ mask] = mint::raw(x); } std::vector<mint> c = bitwise_or_convolution(a, b); for (int i = 0; i < (1 << n); i++) { std::cout << c[i ^ mask].val() << " \n"[i == (1 << n) - 1]; } }