convolution/convolution_xor.hpp

• View this file on GitHub
• Last update: 2025-01-06 05:33:43+09:00
• Include: #include "convolution/convolution_xor.hpp"

Depends on

• convolution/walsh_hadamard_transform.hpp

Verified with

• verify/yosupo_convolution/convolution_xor.test.cpp

Code

#ifndef KK2_CONVOLUTION_CONVOLUTION_XOR_HPP
#define KK2_CONVOLUTION_CONVOLUTION_XOR_HPP 1

#include <cassert>

#include "walsh_hadamard_transform.hpp"

namespace kk2 {

template <class FPS> FPS convolution_xor(FPS &a, const FPS &b) {
    assert(size(a) == size(b));
    int n = int(size(a)); // == int(size(b)
    if (!n) return {};
    assert((n & -n) == n);
    FPS c(b.begin(), b.end());

    walsh_hadamard_transform(a);
    walsh_hadamard_transform(c);
    for (int i = 0; i < n; i++) a[i] *= c[i];
    inverse_walsh_hadamard_transform(a);

    return a;
}

} // namespace kk2

#endif // KK2_CONVOLUTION_CONVOLUTION_XOR_HPP

#line 1 "convolution/convolution_xor.hpp"



#include <cassert>

#line 1 "convolution/walsh_hadamard_transform.hpp"



#line 5 "convolution/walsh_hadamard_transform.hpp"

namespace kk2 {

template <class FPS> void walsh_hadamard_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) {
                auto x = a[j], y = a[i ^ j];
                a[j] = -x + y, a[i ^ j] = x + y;
            }
        }
    }
}

template <class FPS> void inverse_walsh_hadamard_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) {
                auto x = a[j], y = a[i ^ j];
                a[j] = (-x + y) / 2, a[i ^ j] = (x + y) / 2;
            }
        }
    }
}

} // namespace kk2


#line 7 "convolution/convolution_xor.hpp"

namespace kk2 {

template <class FPS> FPS convolution_xor(FPS &a, const FPS &b) {
    assert(size(a) == size(b));
    int n = int(size(a)); // == int(size(b)
    if (!n) return {};
    assert((n & -n) == n);
    FPS c(b.begin(), b.end());

    walsh_hadamard_transform(a);
    walsh_hadamard_transform(c);
    for (int i = 0; i < n; i++) a[i] *= c[i];
    inverse_walsh_hadamard_transform(a);

    return a;
}

} // namespace kk2

Back to top page