convolution/bitwise_and_convolution.hpp

• View this file on GitHub
• Last update: 2023-03-31 06:51:54+09:00
• Include: #include "convolution/bitwise_and_convolution.hpp"

Depends on

• Fast Zeta / Mobius Transform (高速ゼータ変換・高速メビウス変換) (convolution/fast_zeta_mobius_transform.hpp)

Code

#pragma once

#include "convolution/fast_zeta_mobius_transform.hpp"

// bitwise and convolution
// input: A, B
// output: C
// C_i = \sum_{j \& k = i} A_j B_k
template <class T> std::vector<T> bitwise_and_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = (int)a.size();
    assert(a.size() == b.size());
    assert((n & (n - 1)) == 0);
    fast_zeta_transform_supset(a);
    fast_zeta_transform_supset(b);
    for (int i = 0; i < n; i++) a[i] *= b[i];
    fast_mobius_transform_supset(a);
    return a;
}

#line 2 "convolution/bitwise_and_convolution.hpp"

#line 2 "convolution/fast_zeta_mobius_transform.hpp"

// fast zeta transform (subset)
// input: A
// output: B
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_zeta_transform_subset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i] += a[i ^ j];
            }
        }
    }
}

// fast mobius transform (subset)
// input: B
// output: A
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_mobius_transform_subset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i] -= b[i ^ j];
            }
        }
    }
}

// fast zeta transform (supset)
// input: A
// output: B
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_zeta_transform_supset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i ^ j] += a[i];
            }
        }
    }
}

// fast mobius transform (supset)
// input: B
// output: A
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_mobius_transform_supset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i ^ j] -= b[i];
            }
        }
    }
}
#line 4 "convolution/bitwise_and_convolution.hpp"

// bitwise and convolution
// input: A, B
// output: C
// C_i = \sum_{j \& k = i} A_j B_k
template <class T> std::vector<T> bitwise_and_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = (int)a.size();
    assert(a.size() == b.size());
    assert((n & (n - 1)) == 0);
    fast_zeta_transform_supset(a);
    fast_zeta_transform_supset(b);
    for (int i = 0; i < n; i++) a[i] *= b[i];
    fast_mobius_transform_supset(a);
    return a;
}

Back to top page