Src/Sequence/BitwiseAndConvolution.hpp

• View this file on GitHub
• Last update: 2025-09-23 00:58:48+09:00
• Include: #include "Src/Sequence/BitwiseAndConvolution.hpp"

Depends on

• Superset Zeta/Mobius Transform ( $\emptyset$ の方へ集めるやつ ) (Src/Sequence/SupersetTransform.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/LC/bitwise_and_convolution.test.cpp

Code

#pragma once

#include "SupersetTransform.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

template <class T>
std::vector<T> BitwiseAndConvolution(std::vector<T> a, std::vector<T> b) {
    assert(a.size() and b.size());
    const usize n = std::bit_width(std::max(a.size(), b.size()) - 1);
    a.resize(1 << n);
    b.resize(1 << n);
    SupersetZetaTransform(n, a);
    SupersetZetaTransform(n, b);
    for (usize i = 0 ; i < (usize{1} << n) ; i++)
        a[i] *= b[i];
    SupersetMobiusTransform(n, a);
    return a;
}

} // namespace zawa

#line 2 "Src/Sequence/BitwiseAndConvolution.hpp"

#line 2 "Src/Sequence/SupersetTransform.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/SupersetTransform.hpp"

#include <vector>

namespace zawa {

template <class T>
void SupersetZetaTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] += a[b];
}

template <class T>
void SupersetMobiusTransform(usize n, std::vector<T>& a) {
    for (usize i = 0 ; i < n ; i++)
        for (usize b = ssize(a) ; b-- ; )
            if (b & (usize{1} << i))
                a[b ^ (usize{1} << i)] -= a[b];
}

} // namespace zawa
#line 4 "Src/Sequence/BitwiseAndConvolution.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <utility>
#line 10 "Src/Sequence/BitwiseAndConvolution.hpp"

namespace zawa {

template <class T>
std::vector<T> BitwiseAndConvolution(std::vector<T> a, std::vector<T> b) {
    assert(a.size() and b.size());
    const usize n = std::bit_width(std::max(a.size(), b.size()) - 1);
    a.resize(1 << n);
    b.resize(1 << n);
    SupersetZetaTransform(n, a);
    SupersetZetaTransform(n, b);
    for (usize i = 0 ; i < (usize{1} << n) ; i++)
        a[i] *= b[i];
    SupersetMobiusTransform(n, a);
    return a;
}

} // namespace zawa

Back to top page