zeta_transform
(src/math/zeta_transform.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/math/zeta_transform.hpp"

zeta_transform

(1) void superset_zeta_transform(vector<T>& f, bool inv = false)
(2) void subset_zeta_transform(vector<T>& f, bool inv = false)

長さ $2^N$ の数列 $f$ に対して，

• (1): 上位集合高速ゼータ変換 ( inv = true ならばメビウス変換) を計算します．
• (2): 下位集合高速ゼータ変換 ( inv = true ならばメビウス変換) を計算します．

上位・下位高速ゼータ変換の定義式は以下の通りで，メビウス変換はその逆変換です．

\[(1) ~ g_x = \sum\limits_{i \supseteq x} f_i\] \[(2) ~ g_x = \sum\limits_{i \subseteq x} f_i\]

制約

• 数列 $f$ の長さは $2$ の累乗である．

計算量

• $O(2^N N)$

Depends on

• template (src/template/template.hpp)

Required by

• and_convolution (src/convolution/and_convolution.hpp)
• or_convolution (src/convolution/or_convolution.hpp)

Verified with

• verify/library_checker/convolution/bitwise_and_convolution.test.cpp
• verify/unit_test/convolution/or_convolution.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename T>
void superset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j] += sign * f[j | i];
            }
        }
    }
}
template <typename T>
void subset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j | i] += sign * f[j];
            }
        }
    }
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/zeta_transform.hpp"
template <typename T>
void superset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j] += sign * f[j | i];
            }
        }
    }
}
template <typename T>
void subset_zeta_transform(vector<T>& f, const bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    const int sign = inv ? -1 : 1;
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                f[j | i] += sign * f[j];
            }
        }
    }
}

Back to top page