高速ゼータ変換・高速メビウス変換
(math/zeta_mobius_transform.hpp)

• View this file on GitHub
• Last update: 2022-09-17 18:19:46+09:00
• Include: #include "math/zeta_mobius_transform.hpp"

使い方

• superset_zeta(f): f を $g(S) = \displaystyle \sum_{S\subset T}f(T)$ となる g に置き換える。
• superset_mobius(f): f を $f(S) = \displaystyle \sum_{S \subset T}g(T)$ となる g に置き換える。
• subset_zeta(f): f を $g(S) = \displaystyle \sum_{S \supset T}f(T)$ となる g に置き換える。
• subset_mobius(f): f を $f(S) = \displaystyle \sum_{S \supset T}g(T)$ となる g に置き換える。

制約

• ある非負整数 $n$ が存在して $|f|=2^n$ 。

Required by

• Bitwise And Convolution (math/bitwise_and_convolution.hpp)
• Bitwise Or Convolution (math/bitwise_or_convolution.hpp)

Verified with

• test/library-checker/bitwise_and_convolution.test.cpp
• test/library-checker/bitwise_or_convolution.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>
template <typename mint>
void superset_zeta(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] += f[j | i];
            }
        }
    }
}
template <typename mint>
void superset_mobius(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] -= f[j | i];
            }
        }
    }
}
template <typename mint>
void subset_zeta(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] += f[j];
            }
        }
    }
}
template <typename mint>
void subset_mobius(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] -= f[j];
            }
        }
    }
}

#line 2 "math/zeta_mobius_transform.hpp"
#include <cassert>
#include <vector>
template <typename mint>
void superset_zeta(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] += f[j | i];
            }
        }
    }
}
template <typename mint>
void superset_mobius(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j] -= f[j | i];
            }
        }
    }
}
template <typename mint>
void subset_zeta(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] += f[j];
            }
        }
    }
}
template <typename mint>
void subset_mobius(std::vector<mint>& f) {
    int n = f.size();
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((j & i) == 0) {
                f[j | i] -= f[j];
            }
        }
    }
}

Back to top page