math/xorconvolution.hpp

• View this file on GitHub
• Last update: 2025-08-07 22:45:57+09:00
• Include: #include "math/xorconvolution.hpp"

Depends on

• math/FWT.hpp

Code

#pragma once
#include "FWT"
#include <bits/stdc++.h>
using namespace std;
template <class T>
vector<T> xorconvolution(vector<T>& a, vector<T>& b) {
    int n=1;
    while (n < max((int)a.size(), (int)b.size())) n<<=1;
    vector<T> A(n), B(n);
    for (int i=0; i<(int)a.size(); i++) {
        A[i] = a[i];
    }
    for (int i=0; i<(int)b.size(); i++) {
        B[i] = b[i];
    }
    FWT(A, false);
    FWT(B, false);
    for (int i=0; i<n; i++) {
        A[i] *= B[i];
    }
    FWT(A, true);
    vector<T> re(max((int)a.size(), (int)b.size()));
    for (int i=0; i<max((int)a.size(), (int)b.size()); i++) {
        re[i] = A[i];
    }
    return re;
}

#line 2 "math/FWT.hpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
void FWT(vector<T>& a, bool invert = false) {
    for (int i=1; i<(int)a.size(); i<<=1) {
        for (int j=0; j<(int)a.size(); j++) {
            if ((i & j) == 0) {
                T x = a[j], y = a[i+j];
                a[j] = x + y;
                a[i+j] = x - y;
            }
        }
    }
    if (invert) {
        for (int i=0; i<(int)a.size(); i++) {
            a[i] /= (int)a.size();
        }
    }
}
#line 4 "math/xorconvolution.hpp"
using namespace std;
template <class T>
vector<T> xorconvolution(vector<T>& a, vector<T>& b) {
    int n=1;
    while (n < max((int)a.size(), (int)b.size())) n<<=1;
    vector<T> A(n), B(n);
    for (int i=0; i<(int)a.size(); i++) {
        A[i] = a[i];
    }
    for (int i=0; i<(int)b.size(); i++) {
        B[i] = b[i];
    }
    FWT(A, false);
    FWT(B, false);
    for (int i=0; i<n; i++) {
        A[i] *= B[i];
    }
    FWT(A, true);
    vector<T> re(max((int)a.size(), (int)b.size()));
    for (int i=0; i<max((int)a.size(), (int)b.size()); i++) {
        re[i] = A[i];
    }
    return re;
}

Back to top page