AND畳み込み(Bitwise AND Convolution)
(math/and_convolution.cpp)

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

説明

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

できること

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

使い方

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

Verified with

• test/yosupo_bitwise_and_convolution.test.cpp

Code

template<class T>
void superset_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) v[s ^ i] += v[s];
        }
    }
}

template<class T>
void superset_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) v[s ^ i] -= v[s];
        }
    }
}

template<class T>
vector<T> and_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);
    superset_zeta_transform(a);
    superset_zeta_transform(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    superset_mobius_transform(a);
    return a;
}

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

#line 1 "math/and_convolution.cpp"
template<class T>
void superset_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) v[s ^ i] += v[s];
        }
    }
}

template<class T>
void superset_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) v[s ^ i] -= v[s];
        }
    }
}

template<class T>
vector<T> and_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);
    superset_zeta_transform(a);
    superset_zeta_transform(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    superset_mobius_transform(a);
    return a;
}

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

Back to top page