Fast Zeta / Mobius Transform (高速ゼータ変換・高速メビウス変換)
(convolution/fast_zeta_mobius_transform.hpp)

• View this file on GitHub
• Last update: 2023-03-31 06:51:54+09:00
• Include: #include "convolution/fast_zeta_mobius_transform.hpp"

1. 下位集合に対する高速ゼータ変換
2. 下位集合に対する高速メビウス変換
3. 上位集合に対する高速ゼータ変換
4. 上位集合に対する高速メビウス変換

使用例

• PAST12 O
  • 各 popcount の組合せごとに Bitwise OR Convolution を計 $ O(N^2) $ 回行い、全体の計算量は $ O(N^3 2^N + Q) $ であると思いきや、Fast Mobius Transform をまとめて行うことができるため、全体の計算量は $ O(N^2 2^N + Q) $ である

Required by

• convolution/bitwise_and_convolution.hpp
• convolution/bitwise_or_convolution.hpp

Code

#pragma once

// fast zeta transform (subset)
// input: A
// output: B
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_zeta_transform_subset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i] += a[i ^ j];
            }
        }
    }
}

// fast mobius transform (subset)
// input: B
// output: A
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_mobius_transform_subset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i] -= b[i ^ j];
            }
        }
    }
}

// fast zeta transform (supset)
// input: A
// output: B
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_zeta_transform_supset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i ^ j] += a[i];
            }
        }
    }
}

// fast mobius transform (supset)
// input: B
// output: A
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_mobius_transform_supset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i ^ j] -= b[i];
            }
        }
    }
}

#line 2 "convolution/fast_zeta_mobius_transform.hpp"

// fast zeta transform (subset)
// input: A
// output: B
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_zeta_transform_subset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i] += a[i ^ j];
            }
        }
    }
}

// fast mobius transform (subset)
// input: B
// output: A
// B_i = \sum_{j \subset i} A_j
template <class T> void fast_mobius_transform_subset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i] -= b[i ^ j];
            }
        }
    }
}

// fast zeta transform (supset)
// input: A
// output: B
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_zeta_transform_supset(std::vector<T> &a) {
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                a[i ^ j] += a[i];
            }
        }
    }
}

// fast mobius transform (supset)
// input: B
// output: A
// B_i = \sum_{j \supset i} A_j
template <class T> void fast_mobius_transform_supset(std::vector<T> &b) {
    const int n = (int)b.size();
    assert((n & (n - 1)) == 0);
    for (int j = 1; j < n; j <<= 1) {
        for (int i = 0; i < n; i++) {
            if (i & j) {
                b[i ^ j] -= b[i];
            }
        }
    }
}

Back to top page