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_and_convolution.hpp" #include <atcoder/modint> #include <iostream> using mint = atcoder::modint998244353; int main() { int n; std::cin >> n; std::vector<mint> a(1 << n), b(1 << n); for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; a[i] = mint::raw(x); } for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; b[i] = mint::raw(x); } std::vector<mint> c = bitwise_and_convolution(a, b); for (int i = 0; i < (1 << n); i++) { std::cout << c[i].val() << " \n"[i == (1 << n) - 1]; } }
#line 1 "test/library-checker/bitwise_and_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_and_convolution.hpp" template <typename mint> std::vector<mint> bitwise_and_convolution(std::vector<mint> a, std::vector<mint> b) { superset_zeta(a); superset_zeta(b); for (int i = 0; i < int(a.size()); i++) { a[i] *= b[i]; } superset_mobius(a); return a; } #line 3 "test/library-checker/bitwise_and_convolution.test.cpp" #include <atcoder/modint> #include <iostream> using mint = atcoder::modint998244353; int main() { int n; std::cin >> n; std::vector<mint> a(1 << n), b(1 << n); for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; a[i] = mint::raw(x); } for (int i = 0; i < (1 << n); i++) { int x; std::cin >> x; b[i] = mint::raw(x); } std::vector<mint> c = bitwise_and_convolution(a, b); for (int i = 0; i < (1 << n); i++) { std::cout << c[i].val() << " \n"[i == (1 << n) - 1]; } }