Superset Zeta/Mobius Transform ( $\emptyset$ の方へ集めるやつ )
(Src/Sequence/SupersetTransform.hpp)

• View this file on GitHub
• Last update: 2025-09-23 00:58:48+09:00
• Include: #include "Src/Sequence/SupersetTransform.hpp"

概要

$n$ 要素の集合に関するゼータ・メビウス変換で特に上位集合に関して集めてくるもの。

ここでのゼータ変換は $B_{S} = \sum_{S\subseteq T} A_{T}$ なる $B$ を計算し、メビウス変換はその逆変換。

自分は $\emptyset$ の方向へ累積和を取るやつと覚えている。

ライブラリの使い方

void SupersetZetaTransform(usize n, std::vector<T>& a)
void SupersetMobiusTransform(usize n, std::vector<T>& a)

$n$ も指定する

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/Sequence/BitwiseAndConvolution.hpp

Verified with

• Test/LC/bitwise_and_convolution.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <vector>

namespace zawa {

template <class T>
void SupersetZetaTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] += a[b];
}

template <class T>
void SupersetMobiusTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] -= a[b];
}

} // namespace zawa

#line 2 "Src/Sequence/SupersetTransform.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/SupersetTransform.hpp"

#include <vector>

namespace zawa {

template <class T>
void SupersetZetaTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] += a[b];
}

template <class T>
void SupersetMobiusTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] -= a[b];
}

} // namespace zawa

Back to top page