test/math/and_convolution.test.cpp

• View this file on GitHub
• Last update: 2024-11-23 15:36:46+09:00
• Problem: https://judge.yosupo.jp/problem/bitwise_and_convolution

Depends on

• math/Bitwise_Convolution.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution"
#include "../../math/Bitwise_Convolution.hpp"
#include <iostream>
#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::vector<mint> A(1 << N), B(1 << N);
    int v;
    for (auto &a : A) std::cin >> v, a = v;
    for (auto &b : B) std::cin >> v, b = v;
    auto ans = po167::and_convolution(A, B);
    for (auto &c : ans) std::cout << c.val() << " ";
}

#line 1 "test/math/and_convolution.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bitwise_and_convolution"
#line 2 "math/Bitwise_Convolution.hpp"
#include <vector>
#include <cassert>
namespace po167{
//https://kazuma8128.hatenablog.com/entry/2018/05/31/144519
template<class T>
void and_fwt(std::vector<T> &f){
    int n = f.size();
    for (int i = 1; i < n; i <<= 1){
        for (int j = 0; j < n; j++){
            if ((j & i) == 0){
                f[j] = f[j] + f[j | i];
            }
        }
    }
}
template<class T>
void and_ifwt(std::vector<T> &f){
    int n = f.size();
    for (int i = 1; i < n; i <<= 1){
        for (int j = 0; j < n; j++){
            if ((j & i) == 0){
                f[j] = f[j] - f[j | i];
            }
        }
    }
}
template<class T>
std::vector<T> and_convolution(std::vector<T> p, std::vector<T> q){
    int n = p.size();
    assert(n == (int)q.size());
    and_fwt(p), and_fwt(q);
    for (int i = 0; i < n; i++) p[i] = p[i] * q[i];
    and_ifwt(p);
    return p;
}

template<class T>
void or_fwt(std::vector<T> &f){
    int n = f.size();
    for (int i = 1; i < n; i <<= 1){
        for (int j = 0; j < n; j++){
            if (j & i){
                f[j] = f[j] + f[j ^ i];
            }
        }
    }
}
template<class T>
void or_ifwt(std::vector<T> &f){
    int n = f.size();
    for (int i = 1; i < n; i <<= 1){
        for (int j = 0; j < n; j++){
            if (j & i){
                f[j] = f[j] - f[j ^ i];
            }
        }
    }
}

template<class T>
std::vector<T> or_convolution(std::vector<T> p, std::vector<T> q){
    int n = p.size();
    assert(n == (int)q.size());
    or_fwt(p), or_fwt(q);
    for (int i = 0; i < n; i++) p[i] = p[i] * q[i];
    or_ifwt(p);
    return p;
}

template<class T>
void xor_fwt(std::vector<T> &f){
    int n = f.size();
    for (int i = 1; i < n; i <<= 1){
        for (int j = 0; j < n; j++){
            if (j & i){
                T x = f[j ^ i], y = f[j];
                f[j ^ i] = x + y;
                f[j]     = x - y;
            }
        }
    }
}

template<class T>
std::vector<T> xor_convolution(std::vector<T> p, std::vector<T> q){
    int n = p.size();
    assert(n == (int)q.size());
    xor_fwt(p), xor_fwt(q);
    for (int i = 0; i < n; i++) p[i] = p[i] * q[i];
    xor_fwt(p);
    T inv = (T)(1) / (T)(n);
    for (int i = 0; i < n; i++) p[i] = p[i] * inv;
    return p;
}

};
#line 3 "test/math/and_convolution.test.cpp"
#include <iostream>
#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::vector<mint> A(1 << N), B(1 << N);
    int v;
    for (auto &a : A) std::cin >> v, a = v;
    for (auto &b : B) std::cin >> v, b = v;
    auto ans = po167::and_convolution(A, B);
    for (auto &c : ans) std::cout << c.val() << " ";
}

Back to top page