Bitwise Zeta / Möbius Transform

components/bitwise_zeta.hpp · GitHub で見る

共通ページ

#include "lib/components/bitwise_zeta.hpp"

std::vector<long long> a{1, 2, 3, 4};
bitwise_zeta(a); // {1,3,4,10}
bitwise_zeta<true>(a); // {1,2,3,4}

操作	内容・返り値	計算量
bitwise_zeta<inverse = false,superset = false>(a)	配列を部分集合ゼータ変換。superset = true は上位集合、inverse = true はメビウス変換	\(O(n\log n)\)

添字を集合の bitmask として扱います。既定の変換後は a[S] が元の a[T] のうち T が S の部分集合であるものの和になります。例の添字 3 は {0,1} なので全 4 要素の和 10 です。返り値は void で、渡した配列が書き換わります。元に戻すときも、同じ superset の指定で逆変換します。

bitwise_zeta<inverse = false, superset = false>(a) は部分集合和、superset = true なら上位集合和を計算します。inverse = true は逆変換です。長さは 2 の冪とします。

長さを \(n\) として時間は \(O(n\log n)\)、追加空間は \(O(1)\) です。要素の演算は \(O(1)\) とします。

検証コード

• test/bitwise_and_convolution.test.cpp
• test/bitwise_xor_convolution.test.cpp

コード

#ifndef BITWISE_ZETA_HPP
#define BITWISE_ZETA_HPP

#include <bit>
#include <cassert>
#include <cstddef>
#include <vector>

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

namespace bitwise_zeta_detail {
template <bool inverse, bool superset, class T>
void stages(std::vector<T> &a, std::size_t start, std::size_t n, std::size_t half) {
	auto step = [&](std::size_t low, std::size_t high) {
		T &to = a[superset ? low : high];
		const T &from = a[superset ? high : low];
		if constexpr (inverse) to -= from;
		else to += from;
	};
	for (; half < n / 2; half *= 4)
		for (std::size_t block = start; block < start + n; block += 4 * half)
			for (std::size_t j = block; j < block + half; ++j) {
				step(j, j + half);
				step(j + 2 * half, j + 3 * half);
				step(j, j + 2 * half);
				step(j + half, j + 3 * half);
			}
	if (half < n)
		for (std::size_t j = start; j < start + half; ++j) step(j, j + half);
}
}

template <bool inverse = false, bool superset = false, class T>
void bitwise_zeta(std::vector<T> &a) {
	assert(a.empty() || std::has_single_bit(a.size()));
	constexpr std::size_t block = 1024;
	if (a.size() <= block) bitwise_zeta_detail::stages<inverse, superset>(a, 0, a.size(), 1);
	else {
		for (std::size_t start = 0; start < a.size(); start += block)
			bitwise_zeta_detail::stages<inverse, superset>(a, start, block, 1);
		bitwise_zeta_detail::stages<inverse, superset>(a, 0, a.size(), block);
	}
}

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#endif

Back to top page