convolution/or_convolution.hpp

• View this file on GitHub
• Last update: 2022-07-17 14:27:07+09:00
• Include: #include "convolution/or_convolution.hpp"

Verified with

• convolution/test/bitwise_or_convolution.test.cpp

Code

#pragma once

#include <vector>
#include <cassert>

template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    int n = 0;
    while ((1 << n) < (int) a.size()) {
        ++n;
    }
    assert((int) a.size() == (1 << n));
    assert((int) b.size() == (1 << n));
    
    for (int d = 0; d < n; ++d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                a[i] += a[i ^ (1 << d)];
                b[i] += b[i ^ (1 << d)];
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        a[i] *= b[i];
    }
    for (int d = 0; d < n; ++d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                a[i] -= a[i ^ (1 << d)];
            }
        }
    }
    
    return a;
}

#line 2 "convolution/or_convolution.hpp"

#include <vector>
#include <cassert>

template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    int n = 0;
    while ((1 << n) < (int) a.size()) {
        ++n;
    }
    assert((int) a.size() == (1 << n));
    assert((int) b.size() == (1 << n));
    
    for (int d = 0; d < n; ++d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                a[i] += a[i ^ (1 << d)];
                b[i] += b[i ^ (1 << d)];
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        a[i] *= b[i];
    }
    for (int d = 0; d < n; ++d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                a[i] -= a[i ^ (1 << d)];
            }
        }
    }
    
    return a;
}

Back to top page