Algorithm/superset_transform.hpp

• View this file on GitHub
• Last update: 2024-07-31 11:08:52+09:00
• Include: #include "Algorithm/superset_transform.hpp"

Required by

• Convolution/bitwise_and_convolution.hpp

Verified with

• verify/bitwise_and_convolution.test.cpp
• verify/superset_transform.test.cpp

Code

template<class S, S (*op)(S, S)> vector<S> superset_zeta_transform (vector<S> f, int n) {
    rep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) == 0) { // if i in s
                f[s] = op(f[s], f[s ^ (1 << i)]);
            }
        }
    }
    return f;
}

template<class S, S (*op)(S, S), S (*inv)(S)> vector<S> superset_mobius_transform (vector<S> f, int n) {
    rrep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) == 0) { // if i in s
                f[s] = op(f[s], inv(f[s ^ (1 << i)]));
                //f[s] = f[s] -  f[s ^ (1 << i)];
            }
        }
    }
    return f;
}

#line 1 "Algorithm/superset_transform.hpp"
template<class S, S (*op)(S, S)> vector<S> superset_zeta_transform (vector<S> f, int n) {
    rep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) == 0) { // if i in s
                f[s] = op(f[s], f[s ^ (1 << i)]);
            }
        }
    }
    return f;
}

template<class S, S (*op)(S, S), S (*inv)(S)> vector<S> superset_mobius_transform (vector<S> f, int n) {
    rrep(i, 0, n) {
        rep(s, 0, 1LL << n) {
            if((s & (1 << i)) == 0) { // if i in s
                f[s] = op(f[s], inv(f[s ^ (1 << i)]));
                //f[s] = f[s] -  f[s ^ (1 << i)];
            }
        }
    }
    return f;
}

Back to top page