下位集合のゼータ・メビウス変換
(library/polynomial/fft/subset_zeta_moebius_transform.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/polynomial/fft/subset_zeta_moebius_transform.hpp"

下位集合のゼータ・メビウス変換

できること

• 詳しい説明

計算量

$O(N \cdot 2^N)$

使い方

subset_zeta_transform(f);
subset_moebius_transform(f);

Required by

• Bitwise畳み込みOR (library/polynomial/fft/convolution_bitwise_or.hpp)

Verified with

• Bitwise畳み込みORのテスト (tests/polynomial.fft.convolution_bitwise_or.test.cpp)

Code

#pragma once
template <typename T> void subset_zeta_transform(vector<T> &f) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0ll);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                f[j + k + i] += f[j + k];
            }
        }
    }
}
template <typename T> void subset_moebius_transform(vector<T> &f) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0ll);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                f[j + k + i] -= f[j + k];
            }
        }
    }
}

#line 2 "library/polynomial/fft/subset_zeta_moebius_transform.hpp"
template <typename T> void subset_zeta_transform(vector<T> &f) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0ll);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                f[j + k + i] += f[j + k];
            }
        }
    }
}
template <typename T> void subset_moebius_transform(vector<T> &f) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0ll);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                f[j + k + i] -= f[j + k];
            }
        }
    }
}

Back to top page