Convolution/bitwise_and_convolution.hpp

View this file on GitHub
Last update: 2025-01-11 07:38:14+09:00
Include: #include "Convolution/bitwise_and_convolution.hpp"

Depends on

Algorithm/superset_transform.hpp

Verified with

verify/bitwise_and_convolution.test.cpp

Code

#include "../Algorithm/superset_transform.hpp"
// i and j = k <-> i and j が k の superset (⇔ i, jがともにkのsuperset)
template<class S, S (*op)(S, S), S (*inv)(S),  S(*zero)()> vec<S> bitwise_and_convolution(vec<S> A, vec<S> B) {
    ll lg = 1;
    while(A.size() > (1LL << lg)) lg++;
    while(B.size() > (1LL << lg)) lg++;
    A.resize(1LL << lg, zero());
    B.resize(1LL << lg, zero());

    vec<S> FA = superset_zeta_transform<S, op>(A, lg);
    vec<S> FB = superset_zeta_transform<S, op>(B, lg);
    rep(i, 0, 1 << lg) FA[i] *= FB[i];
    vec<S> f = superset_mobius_transform<S, op, inv>(FA, lg);
    return f;
}
//以降の項について、0である。

#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;
}
#line 2 "Convolution/bitwise_and_convolution.hpp"
// i and j = k <-> i and j が k の superset (⇔ i, jがともにkのsuperset)
template<class S, S (*op)(S, S), S (*inv)(S),  S(*zero)()> vec<S> bitwise_and_convolution(vec<S> A, vec<S> B) {
    ll lg = 1;
    while(A.size() > (1LL << lg)) lg++;
    while(B.size() > (1LL << lg)) lg++;
    A.resize(1LL << lg, zero());
    B.resize(1LL << lg, zero());

    vec<S> FA = superset_zeta_transform<S, op>(A, lg);
    vec<S> FB = superset_zeta_transform<S, op>(B, lg);
    rep(i, 0, 1 << lg) FA[i] *= FB[i];
    vec<S> f = superset_mobius_transform<S, op, inv>(FA, lg);
    return f;
}
//以降の項について、0である。