This documentation is automatically generated by online-judge-tools/verification-helper
#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];
}
}