Bitwise Convolution
(Convolution/bitwise.hpp)

• View this file on GitHub
• Last update: 2023-01-16 20:41:46+09:00
• Include: #include "Convolution/bitwise.hpp"

使い方

void zeta(vector<T>& a): $a’[n]=\sum_{k \subset n} a[k]$ を計算。
void mobius(vector<T>& a): $a[n]=\sum_{k \subset n} a’[k]$ を計算。
void fwt(vector<T>& a): $a$ と $n$ 次 Hadamard 行列の積を計算。

Verified with

• Verify/LC_bitwise_and_convolution.test.cpp
• Verify/LC_bitwise_xor_convolution.test.cpp

Code

#pragma once

namespace Bitwise{
    template<typename T>void zeta(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]+=a[mask^(1<<k)];
        }
    }
    template<typename T>void mobius(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]-=a[mask^(1<<k)];
        }
    }
    template<typename T>void fwt(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(!(mask>>k&1)){
                T x=a[mask],y=a[mask|(1<<k)];
                a[mask]=x+y,a[mask|(1<<k)]=x-y;
            }
        }
    }
};

/**
 * @brief Bitwise Convolution
 * @docs docs/bitwise.md
 */

#line 2 "Convolution/bitwise.hpp"

namespace Bitwise{
    template<typename T>void zeta(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]+=a[mask^(1<<k)];
        }
    }
    template<typename T>void mobius(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]-=a[mask^(1<<k)];
        }
    }
    template<typename T>void fwt(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(!(mask>>k&1)){
                T x=a[mask],y=a[mask|(1<<k)];
                a[mask]=x+y,a[mask|(1<<k)]=x-y;
            }
        }
    }
};

/**
 * @brief Bitwise Convolution
 * @docs docs/bitwise.md
 */

Back to top page