OR畳み込み(Bitwise OR Convolution)
(math/or_convolution.cpp)

• View this file on GitHub
• Last update: 2026-03-10 23:38:19+09:00

説明

bitwise OR 畳み込みを計算する。 c[S] = Σ_{A | B = S} a[A] b[B] を返す。 計算量は $O(N log N)$。

できること

• void subset_zeta_transform(vector<T>& v) subset zeta transform をその場適用する
• void subset_mobius_transform(vector<T>& v) subset zeta transform の逆変換をその場適用する
• vector<T> or_convolution(vector<T> a, vector<T> b) OR 畳み込みを返す。長さは大きい方に合わせて 2 冪へ拡張する

使い方

T には +, -, *, +=, -=, *= が必要。 OR 畳み込み以外にも subset zeta / mobius transform を単体で使える。

Verified with

• test/yosupo_bitwise_or_convolution.test.cpp

Code

template<class T>
void subset_zeta_transform(vector<T> &v){
    int n = 1;
    while (n < (int)v.size()) n <<= 1;
    v.resize(n);
    for (int i = 1; i < n; i <<= 1) {
        for (int s = 0; s < n; ++s) {
            if ((s & i) == 0) v[s | i] += v[s];
        }
    }
}

template<class T>
void subset_mobius_transform(vector<T> &v){
    int n = 1;
    while (n < (int)v.size()) n <<= 1;
    v.resize(n);
    for (int i = 1; i < n; i <<= 1) {
        for (int s = 0; s < n; ++s) {
            if ((s & i) == 0) v[s | i] -= v[s];
        }
    }
}

template<class T>
vector<T> or_convolution(vector<T> a, vector<T> b){
    int n = 1;
    while (n < (int)a.size() || n < (int)b.size()) n <<= 1;
    a.resize(n);
    b.resize(n);
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    subset_mobius_transform(a);
    return a;
}

/**
 * @brief OR畳み込み(Bitwise OR Convolution)
 */

#line 1 "math/or_convolution.cpp"
template<class T>
void subset_zeta_transform(vector<T> &v){
    int n = 1;
    while (n < (int)v.size()) n <<= 1;
    v.resize(n);
    for (int i = 1; i < n; i <<= 1) {
        for (int s = 0; s < n; ++s) {
            if ((s & i) == 0) v[s | i] += v[s];
        }
    }
}

template<class T>
void subset_mobius_transform(vector<T> &v){
    int n = 1;
    while (n < (int)v.size()) n <<= 1;
    v.resize(n);
    for (int i = 1; i < n; i <<= 1) {
        for (int s = 0; s < n; ++s) {
            if ((s & i) == 0) v[s | i] -= v[s];
        }
    }
}

template<class T>
vector<T> or_convolution(vector<T> a, vector<T> b){
    int n = 1;
    while (n < (int)a.size() || n < (int)b.size()) n <<= 1;
    a.resize(n);
    b.resize(n);
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    subset_mobius_transform(a);
    return a;
}

/**
 * @brief OR畳み込み(Bitwise OR Convolution)
 */

Back to top page