xor_convolution
(src/convolution/xor_convolution.hpp)

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

xor_convolution

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

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

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

を計算します．

制約

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

計算量

• $O(2^N N)$

Depends on

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

Verified with

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

Code

#pragma once
#include "../template/template.hpp"
#include "../math/walsh_hadamard_transform.hpp"
template <typename T>
vector<T> xor_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);
    walsh_hadamard_transform(a);
    walsh_hadamard_transform(b);
    for(int i = 0; i < (int)a.size(); ++i) a[i] *= b[i];
    walsh_hadamard_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/walsh_hadamard_transform.hpp"
template <typename T>
void walsh_hadamard_transform(vector<T>& f, const bool inv = false) {
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                const T x = f[j], y = f[j | i];
                f[j] = x + y, f[j | i] = x - y;
            }
        }
    }
    if(inv) {
        if constexpr(is_integral<T>::value) {
            for(auto& x : f) x /= n;
        } else {
            const T invn = T(1) / T(f.size());
            for(auto& x : f) x *= invn;
        }
    }
}
#line 4 "src/convolution/xor_convolution.hpp"
template <typename T>
vector<T> xor_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);
    walsh_hadamard_transform(a);
    walsh_hadamard_transform(b);
    for(int i = 0; i < (int)a.size(); ++i) a[i] *= b[i];
    walsh_hadamard_transform(a, true);
    return a;
}

Back to top page