Depends on
Required by
Verified with
Code
#pragma once
#include <bit>
#include <ranges>
#include "snippet/aliases.hpp"
namespace uni {
namespace superset_transform {
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void zeta ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j ] += range [ j | i ];
}
}
}
}
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void mobius ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j ] -= range [ j | i ];
}
}
}
}
} // namespace superset_transform
namespace subset_transform {
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void zeta ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j | i ] += range [ j ];
}
}
}
}
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void mobius ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j | i ] -= range [ j ];
}
}
}
}
} // namespace subset_transform
} // namespace uni #line 2 "numeric/subset_superset_transform.hpp"
#include <bit>
#include <ranges>
#line 2 "snippet/aliases.hpp"
#include <cstdint>
#include <utility>
#include <vector>
#line 8 "snippet/aliases.hpp"
#line 2 "internal/dev_env.hpp"
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true ;
inline constexpr bool NO_EXCEPT = false ;
#else
inline constexpr bool DEV_ENV = false ;
inline constexpr bool NO_EXCEPT = true ;
#endif // LOCAL_JUDGE
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
#line 2 "snippet/internal/types.hpp"
#line 4 "snippet/internal/types.hpp"
namespace uni {
using i16 = std :: int16_t ;
using u16 = std :: uint16_t ;
using i32 = std :: int32_t ;
using u32 = std :: uint32_t ;
using i64 = std :: int64_t ;
using u64 = std :: uint64_t ;
#ifdef __GNUC__
using i128 = __int128_t ;
using u128 = __uint128_t ;
using f128 = __float128 ;
#endif
using uint = unsigned ;
using ll = long long ;
using ull = unsigned long long ;
using ld = long double ;
} // namespace uni
#line 12 "snippet/aliases.hpp"
#define until(...) while(!(__VA_ARGS__))
#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }
#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))
#define $F first
#define $S second
namespace uni {
constexpr char LN = '\n' ;
constexpr char SPC = ' ' ;
constexpr std :: pair < int , int > DIRS4 [] = { { - 1 , 0 }, { 0 , 1 }, { 1 , 0 }, { 0 , - 1 } };
constexpr std :: pair < int , int > DIRS4P [] = { { - 1 , 0 }, { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { 0 , 0 } };
constexpr std :: pair < int , int > DIRS8 [] = { { - 1 , 0 }, { - 1 , 1 }, { 0 , 1 }, { 1 , 1 }, { 1 , 0 }, { 1 , - 1 }, { 0 , - 1 }, { - 1 , - 1 } };
constexpr std :: pair < int , int > DIRS8P [] = { { - 1 , 0 }, { - 1 , 1 }, { 0 , 1 }, { 1 , 1 }, { 1 , 0 }, { 1 , - 1 }, { 0 , - 1 }, { - 1 , - 1 }, { 0 , 0 } };
template < class T > using spair = std :: pair < T , T > ;
} // namespace uni
namespace std {
using bit_reference = std :: vector < bool >:: reference ;
bit_reference operator |= ( bit_reference a , const bool b ) noexcept ( NO_EXCEPT ) { return a = a | b ; }
bit_reference operator &= ( bit_reference a , const bool b ) noexcept ( NO_EXCEPT ) { return a = a & b ; }
}
#line 8 "numeric/subset_superset_transform.hpp"
namespace uni {
namespace superset_transform {
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void zeta ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j ] += range [ j | i ];
}
}
}
}
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void mobius ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j ] -= range [ j | i ];
}
}
}
}
} // namespace superset_transform
namespace subset_transform {
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void zeta ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j | i ] += range [ j ];
}
}
}
}
template < std :: ranges :: random_access_range R , std :: unsigned_integral Bit = std :: uint32_t >
void mobius ( R & range ) {
const auto n = std :: ranges :: size ( range );
assert ( std :: has_single_bit ( n ));
for ( Bit i = 1 ; i < n ; i <<= 1 ) {
for ( Bit j = 0 ; j < n ; ++ j ) {
if (( j & i ) == 0 ) {
range [ j | i ] -= range [ j ];
}
}
}
}
} // namespace subset_transform
} // namespace uni Back to top page
numeric/subset_superset_transform.hpp