convolution/xor_convolution.cpp

• View this file on GitHub
• Last update: 2021-10-02 08:42:19+09:00

Verified with

• test/yosupo-bitwise_xor_convolution.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
using namespace std;

class xorConvolution {
    template <typename T>
    static void FWT(vector<T>& f) {
        int n = f.size();
        for(int i = 1; i < n; i <<= 1)
            for(int j = 0; j < n; j++)
                if((j & i) == 0) {
                    T x = f[j], y = f[j | i];
                    f[j] = x + y, f[j | i] = x - y;
                }
    }

public:
    template <typename T>
    static vector<T> convolution(vector<T> f, vector<T> g) {
        int sz = 1, n = max(f.size(), g.size());
        while(sz < n) sz <<= 1;
        f.resize(sz);
        g.resize(sz);
        FWT(f);
        FWT(g);
        for(int i = 0; i < sz; i++) f[i] *= g[i];
        FWT(f);
        for(int i = 0; i < sz; i++) f[i] /= sz;
        return f;
    }
};

#line 2 "convolution/xor_convolution.cpp"
#include <bits/stdc++.h>
using namespace std;

class xorConvolution {
    template <typename T>
    static void FWT(vector<T>& f) {
        int n = f.size();
        for(int i = 1; i < n; i <<= 1)
            for(int j = 0; j < n; j++)
                if((j & i) == 0) {
                    T x = f[j], y = f[j | i];
                    f[j] = x + y, f[j | i] = x - y;
                }
    }

public:
    template <typename T>
    static vector<T> convolution(vector<T> f, vector<T> g) {
        int sz = 1, n = max(f.size(), g.size());
        while(sz < n) sz <<= 1;
        f.resize(sz);
        g.resize(sz);
        FWT(f);
        FWT(g);
        for(int i = 0; i < sz; i++) f[i] *= g[i];
        FWT(f);
        for(int i = 0; i < sz; i++) f[i] /= sz;
        return f;
    }
};

Back to top page