Set Zeta/Mobius Transform
(lib/convolution/set_zeta_mobius_transform.hpp)

• View this file on GitHub
• Last update: 2024-11-13 13:43:26+09:00
• Include: #include "lib/convolution/set_zeta_mobius_transform.hpp"

Required by

• Bitwise AND Convolution (lib/convolution/bitwise_and_convolution.hpp)
• Bitwise OR Convolution (lib/convolution/bitwise_or_convolution.hpp)

Verified with

• test/library_checker/convolution/bitwise_and_convolution.test.cpp
• test/library_checker/convolution/bitwise_and_convolution_1.test.cpp

Code

#pragma once

/**
 * @brief Set Zeta/Mobius Transform
 */

#include <vector>
#include <cassert>

template <typename T>
void superset_zeta_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void superset_mobius_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void subset_zeta_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void subset_mobius_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 "lib/convolution/set_zeta_mobius_transform.hpp"

/**
 * @brief Set Zeta/Mobius Transform
 */

#include <vector>
#include <cassert>

template <typename T>
void superset_zeta_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void superset_mobius_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void subset_zeta_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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 T>
void subset_mobius_transform(std::vector<T> &f){
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    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