library

This documentation is automatically generated by online-judge-tools/verification-helper


Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

:heavy_check_mark: Bitwise Convolution
(Convolution/bitwise.hpp)

使い方

void zeta(vector<T>& a): $b[n]=\sum_{k \subset n} a[k]$ なる $b$ を計算。
void mobius(vector<T>& a): $a[n]=\sum_{k \subset n} b[k]$ なる $b$ を計算。
void fwt(vector<T>& a): $b[n]=\sum_k (-1)^{popcount(n \& k)} a[k]$ なる $b$ を計算。

Verified with

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