Math/OrConvolution.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/OrConvolution.hpp"

Code

// ret_k = sum a_i * b_j, i|j=k 
template<typename T>
vector<T> OrConvolution(vector<T> a,vector<T> b){
    assert(a.size()==b.size());
    int n=(int)a.size();
    vector<T> ret(n);
    // FWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0) a[i|j]+=a[j],b[i|j]+=b[j];
    }
    for(int i=0;i<n;i++) ret[i]=a[i]*b[i];
    // IFWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0) ret[j|i]-=ret[j];
    }
    return ret;
}

#line 1 "Math/OrConvolution.hpp"
// ret_k = sum a_i * b_j, i|j=k 
template<typename T>
vector<T> OrConvolution(vector<T> a,vector<T> b){
    assert(a.size()==b.size());
    int n=(int)a.size();
    vector<T> ret(n);
    // FWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0) a[i|j]+=a[j],b[i|j]+=b[j];
    }
    for(int i=0;i<n;i++) ret[i]=a[i]*b[i];
    // IFWT
    for(int i=1;i<n;i<<=1)for(int j=0;j<n;j++){
        if((i&j)==0) ret[j|i]-=ret[j];
    }
    return ret;
}

Back to top page