test/convolution/bitwise_or_convolution.test.cpp

• View this file on GitHub
• Last update: 2026-07-15 17:18:58+00:00
• Problem: https://judge.yosupo.jp/problem/bitwise_and_convolution

Depends on

• convolution/or.hpp
• transform/subset_mobius.hpp
• transform/subset_zeta.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution"

#include "convolution/or.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>
using Z = atcoder::modint998244353;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N;
    std::cin >> N;
    std::vector<Z> A(1 << N);
    for (auto i = 0; i < (1 << N); ++i) {
        int x;
        std::cin >> x;
        A[i] = x;
    }
    std::vector<Z> B(1 << N);
    for (auto i = 0; i < (1 << N); ++i) {
        int x;
        std::cin >> x;
        B[i] = x;
    }
    std::ranges::reverse(A);
    std::ranges::reverse(B);
    auto C = or_convolution(A, B);
    std::ranges::reverse(C);
    for (auto i = 0; i < (1 << N); ++i) {
        std::cout << C[i].val() << " ";
    }
}

#line 1 "test/convolution/bitwise_or_convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution"

#line 1 "convolution/or.hpp"



#line 1 "transform/subset_mobius.hpp"



#include <bit>
#include <cassert>
#include <vector>

template <typename T> void subset_mobius_transform(std::vector<T> &g) {
    assert(std::has_single_bit(g.size()));
    auto n = int(std::countr_zero(g.size()));
    for (auto i = 0; i < n; ++i) {
        for (auto s = 0; s < (1 << n); ++s) {
            if (s & (1 << i)) {
                g[s] -= g[s ^ (1 << i)];
            }
        }
    }
}


#line 1 "transform/subset_zeta.hpp"



#line 7 "transform/subset_zeta.hpp"

template <typename T> void subset_zeta_transform(std::vector<T> &f) {
    assert(std::has_single_bit(f.size()));
    auto n = int(std::countr_zero(f.size()));
    for (auto i = 0; i < n; ++i) {
        for (auto s = 0; s < (1 << n); ++s) {
            if (s & (1 << i)) {
                f[s] += f[s ^ (1 << i)];
            }
        }
    }
}


#line 8 "convolution/or.hpp"

template <typename T> std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    assert(a.size() == b.size());
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for (auto i = 0; i < int(a.size()); ++i) {
        a[i] *= b[i];
    }
    subset_mobius_transform(a);
    return a;
}


#line 4 "test/convolution/bitwise_or_convolution.test.cpp"
#include <atcoder/modint>
#include <bits/stdc++.h>
using Z = atcoder::modint998244353;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N;
    std::cin >> N;
    std::vector<Z> A(1 << N);
    for (auto i = 0; i < (1 << N); ++i) {
        int x;
        std::cin >> x;
        A[i] = x;
    }
    std::vector<Z> B(1 << N);
    for (auto i = 0; i < (1 << N); ++i) {
        int x;
        std::cin >> x;
        B[i] = x;
    }
    std::ranges::reverse(A);
    std::ranges::reverse(B);
    auto C = or_convolution(A, B);
    std::ranges::reverse(C);
    for (auto i = 0; i < (1 << N); ++i) {
        std::cout << C[i].val() << " ";
    }
}

Back to top page