and_convolution
(src/convolution/and_convolution.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/convolution/and_convolution.hpp"

and_convolution

vector<T> and_convolution(vector<T> a, vector<T> b)

AND畳み込みを行います．
長さ $2^N$ の数列 $a$ と $b$ から，長さ $2^N$ の数列，

\[c_k = \sum\limits_{i \& j = k} a_i b_j\]

を計算します．

制約

• 数列 $a$ と $b$ の長さは等しい．
• 数列 $a$ と $b$ の長さは $2$ の累乗である．

計算量

• $O(2^N N)$

Depends on

• zeta_transform (src/math/zeta_transform.hpp)
• template (src/template/template.hpp)

Verified with

• verify/library_checker/convolution/bitwise_and_convolution.test.cpp

Code

#pragma once
#include "../template/template.hpp"
#include "../math/zeta_transform.hpp"
template <typename T>
vector<T> and_convolution(vector<T> a, vector<T> b) {
    const int n = (int)a.size(), m = (int)b.size();
    assert(n == m and (n & (n - 1)) == 0);
    superset_zeta_transform(a);
    superset_zeta_transform(b);
    for(int i = 0; i < (int)a.size(); ++i) a[i] *= b[i];
    superset_zeta_transform(a, true);
    return a;
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/zeta_transform.hpp"
template <typename T>
void superset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j] += sign * f[j | i];
            }
        }
    }
}
template <typename T>
void subset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j | i] += sign * f[j];
            }
        }
    }
}
#line 4 "src/convolution/and_convolution.hpp"
template <typename T>
vector<T> and_convolution(vector<T> a, vector<T> b) {
    const int n = (int)a.size(), m = (int)b.size();
    assert(n == m and (n & (n - 1)) == 0);
    superset_zeta_transform(a);
    superset_zeta_transform(b);
    for(int i = 0; i < (int)a.size(); ++i) a[i] *= b[i];
    superset_zeta_transform(a, true);
    return a;
}

Back to top page