convolution/xor-convolution.hpp

• View this file on GitHub
• Last update: 2024-08-04 01:01:28+07:00
• Include: #include "convolution/xor-convolution.hpp"

Verified with

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

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-07-29
 * Description: Bitwise XOR Convolution.
 * Fast Walsh-Hadamard Transform: $A^\prime[S]=\sum_T(-1)^{|S\&T|}A[T]$.
 * Time: $O(N\log N)$.
 */

template<class T>
void fwht(vector<T> &a){
    int n=(int)a.size();
    assert(n==(n&-n));
    for(int i=1;i<n;i<<=1){
        for(int j=0;j<n;j++){
            if(j&i){
                T &u=a[j^i],&v=a[j];
                tie(u,v)=make_pair(u+v,u-v);
            }
        }
    }
}

template<class T>
vector<T> xor_convolution(vector<T> a,vector<T> b){
    int n=(int)a.size();
    fwht(a);
    fwht(b);
    for(int i=0;i<n;i++)a[i]*=b[i];
    fwht(a);
    T div=T(1)/T(n);
    if(div==T(0)){
        for(auto &x:a)x/=n;
    }else{
        for(auto &x:a)x*=div;
    }
    return a;
}

#line 2 "convolution/xor-convolution.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-07-29
 * Description: Bitwise XOR Convolution.
 * Fast Walsh-Hadamard Transform: $A^\prime[S]=\sum_T(-1)^{|S\&T|}A[T]$.
 * Time: $O(N\log N)$.
 */

template<class T>
void fwht(vector<T> &a){
    int n=(int)a.size();
    assert(n==(n&-n));
    for(int i=1;i<n;i<<=1){
        for(int j=0;j<n;j++){
            if(j&i){
                T &u=a[j^i],&v=a[j];
                tie(u,v)=make_pair(u+v,u-v);
            }
        }
    }
}

template<class T>
vector<T> xor_convolution(vector<T> a,vector<T> b){
    int n=(int)a.size();
    fwht(a);
    fwht(b);
    for(int i=0;i<n;i++)a[i]*=b[i];
    fwht(a);
    T div=T(1)/T(n);
    if(div==T(0)){
        for(auto &x:a)x/=n;
    }else{
        for(auto &x:a)x*=div;
    }
    return a;
}

Back to top page