Fast Zeta/Möbius Transform
(math/set/zeta_moebius_transform.hpp)

View this file on GitHub
Last update: 2024-01-08 17:31:43+09:00
Include: #include "math/set/zeta_moebius_transform.hpp"

Description

下位集合に関する zeta 変換は，写像 $f$ が与えられたとき，以下を満たす写像 $g$ を得る変換である．Möbius 変換は，zeta 変換の逆変換である (つまり，写像 $g$ が与えられたとき，以下を満たす写像 $f$ を得る変換である)．

\[g(S) = \sum_{T \subseteq S} f(T)\]

上位集合に関するものも同様である．

下位集合に関する FZT/FMT を用いると，bitwise OR convolution が高速に計算できる．

\[c_k = \sum_{i\lor j=k} a_i b_j\]

上位集合に関する FZT/FMT を用いると，bitwise AND convolution が高速に計算できる．

\[c_k = \sum_{i\land j=k} a_i b_j\]

Operations

void subset_fzt(vector<T> a)
void superset_fzt(vector<T> a)
- 数列 $a$ を高速 zeta 変換する
- 時間計算量: $O(n\log n)$
void subset_fmt(vector<T> a)
void superset_fmt(vector<T> a)
- 数列 $a$ を高速 Möbius 変換する
- 時間計算量: $O(n\log n)$

Note

畳み込み	変換	逆変換
$\max$	zeta 変換 (累積和，下位)	Möbius 変換 (累積和，下位)
$\min$	zeta 変換 (累積和，上位)	Möbius 変換 (累積和，上位)
$\gcd$	zeta 変換 (倍数)	Möbius 変換 (倍数)
$\mathrm{lcm}$	zeta 変換 (約数)	Möbius 変換 (約数)
$\mathrm{bitwise\ and}$	zeta 変換 (bit，上位)	Möbius 変換 (bit，上位)
$\mathrm{bitwise\ or}$	zeta 変換 (bit，下位)	Möbius 変換 (bit，下位)
$\mathrm{bitwise\ xor}$	Walsh-Hadamard 変換	逆 Walsh-Hadamard 変換
$+$	Fourier 変換，数論変換	逆 Fourier 変換，逆数論変換

Reference

ゼータ変換・メビウス変換を理解する - Qiita
- これを読むと，zeta/Möbius 変換が絡む一連の畳み込み操作に関して完全に理解した気持ちになれる．

Required by

Verified with

Code

#pragma once
#include <bit>
#include <cassert>
#include <vector>

template <typename T>
void superset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] += a[j | i];
        }
    }
}

template <typename T>
void superset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] -= a[j | i];
        }
    }
}

template <typename T>
void subset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] += a[j];
        }
    }
}

template <typename T>
void subset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] -= a[j];
        }
    }
}

#line 2 "math/set/zeta_moebius_transform.hpp"
#include <bit>
#include <cassert>
#include <vector>

template <typename T>
void superset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] += a[j | i];
        }
    }
}

template <typename T>
void superset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] -= a[j | i];
        }
    }
}

template <typename T>
void subset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] += a[j];
        }
    }
}

template <typename T>
void subset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] -= a[j];
        }
    }
}

Fast Zeta/Möbius Transform (math/set/zeta_moebius_transform.hpp)