This documentation is automatically generated by online-judge-tools/verification-helper
#include "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$ を計算。
#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
*/