#ifndef EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#define EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#include <algorithm>
#include <vector>
#include "emthrm/math/convolution/fast_mobius_transform.hpp"
#include "emthrm/math/convolution/fast_zeta_transform.hpp"
namespace emthrm {
template < typename T >
std :: vector < T > or_convolution ( std :: vector < T > a , std :: vector < T > b ,
const T id = 0 ) {
int n = std :: max ( a . size (), b . size ());
a . resize ( n , id );
a = fast_zeta_transform < false > ( a , id );
b . resize ( n , id );
b = fast_zeta_transform < false > ( b , id );
n = a . size ();
for ( int i = 0 ; i < n ; ++ i ) {
a [ i ] *= b [ i ];
}
return fast_mobius_transform < false > ( a );
}
} // namespace emthrm
#endif // EMTHRM_MATH_CONVOLUTION_OR_CONVOLUTION_HPP_
#line 1 "include/emthrm/math/convolution/or_convolution.hpp"
#include <algorithm>
#include <vector>
#line 1 "include/emthrm/math/convolution/fast_mobius_transform.hpp"
#include <bit>
#line 6 "include/emthrm/math/convolution/fast_mobius_transform.hpp"
namespace emthrm {
template < bool ADDS_SUPERSET , typename T >
std :: vector < T > fast_mobius_transform ( std :: vector < T > a , const T id = 0 ) {
const int n = std :: bit_ceil ( a . size ());
a . resize ( n , id );
for ( int i = 1 ; i < n ; i <<= 1 ) {
for ( int s = 0 ; s < n ; ++ s ) {
if ( s & i ) continue ;
if constexpr ( ADDS_SUPERSET ) {
a [ s ] -= a [ s | i ];
} else {
a [ s | i ] -= a [ s ];
}
}
}
return a ;
}
} // namespace emthrm
#line 1 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
#line 5 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
#include <functional>
#line 7 "include/emthrm/math/convolution/fast_zeta_transform.hpp"
namespace emthrm {
template < bool ADDS_SUPERSET , typename Ring , typename BinOp = std :: plus < Ring > >
std :: vector < Ring > fast_zeta_transform (
std :: vector < Ring > a , const Ring ID = 0 , const BinOp bin_op = BinOp ()) {
const int n = std :: bit_ceil ( a . size ());
a . resize ( n , ID );
for ( int i = 1 ; i < n ; i <<= 1 ) {
for ( int s = 0 ; s < n ; ++ s ) {
if ( s & i ) continue ;
if constexpr ( ADDS_SUPERSET ) {
a [ s ] = bin_op ( a [ s ], a [ s | i ]);
} else {
a [ s | i ] = bin_op ( a [ s | i ], a [ s ]);
}
}
}
return a ;
}
} // namespace emthrm
#line 9 "include/emthrm/math/convolution/or_convolution.hpp"
namespace emthrm {
template < typename T >
std :: vector < T > or_convolution ( std :: vector < T > a , std :: vector < T > b ,
const T id = 0 ) {
int n = std :: max ( a . size (), b . size ());
a . resize ( n , id );
a = fast_zeta_transform < false > ( a , id );
b . resize ( n , id );
b = fast_zeta_transform < false > ( b , id );
n = a . size ();
for ( int i = 0 ; i < n ; ++ i ) {
a [ i ] *= b [ i ];
}
return fast_mobius_transform < false > ( a );
}
} // namespace emthrm