Bitwise And Convolution
(math/bitwise_and_convolution.hpp)

• View this file on GitHub
• Last update: 2022-09-17 18:19:46+09:00
• Include: #include "math/bitwise_and_convolution.hpp"

使い方

• bitwise_and_convolution(a, b): $c_k = \displaystyle \sum_{i\&j=k}a_ib_j$ となる数列 c を求める。

制約

• ある非負整数 $n$ が存在して $|a|=|b|=2^n$ 。

Depends on

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

Verified with

• test/library-checker/bitwise_and_convolution.test.cpp

Code

#pragma once
#include "zeta_mobius_transform.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 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;
}

Back to top page