test/library-checker/bitwise_or_convolution.test.cpp

• View this file on GitHub
• Last update: 2024-06-04 13:53:45+09:00
• Problem: https://judge.yosupo.jp/problem/bitwise_and_convolution

Depends on

• Bitwise Or Convolution (math/bitwise_or_convolution.hpp)
• 高速ゼータ変換・高速メビウス変換 (math/zeta_mobius_transform.hpp)

Code

#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];
    }
}

Back to top page