AND・OR・XOR 畳み込み

convolution/bitwise_convolution.hpp · GitHub で見る

共通ページ

#include "lib/convolution/bitwise_convolution.hpp"

std::vector<long long> a{1, 2, 3, 4}, b{5, 6, 7, 8};
auto c = and_convolution(a, b); // {103,52,73,32}
auto d = or_convolution(a, b); // {5,28,43,184}
auto f = xor_convolution(a, b); // {70,68,62,60}

関数	定義	計算量
and_convolution(a, b)	\(\displaystyle c_k = \sum_{i\mathbin{\&}j=k} a_i b_j\)	\(O(N\log N)\)
or_convolution(a, b)	\(\displaystyle c_k = \sum_{i\mathbin{\vert}j=k} a_i b_j\)	\(O(N\log N)\)
xor_convolution(a, b)	\(\displaystyle c_k = \sum_{i\mathbin{\oplus}j=k} a_i b_j\)	\(O(N\log N)\)

添字 i,j に AND・OR・XOR を適用し、その添字へ積 a[i]*b[j] を加えます。入力を変更せず、新しい配列を返します。短い配列の不足分は 0 で埋めます。どちらかが空なら空配列です。

長い方の長さを 2 の冪に切り上げた \(N\) 個を返します。係数は環の要素、XOR ではさらに \(N\) で割れる型を使います。整数型では中間値も型の範囲内とします。

bitwise_zeta<inverse, superset>(a) はその場でゼータ／メビウス変換します。既定は <false, false>、長さは 2 の冪です。walsh_hadamard(a) は非正規化の Hadamard 変換です。

時間 \(O(N \log N)\)、追加空間 \(O(N)\) です。変換のみの追加空間は \(O(1)\) です。

依存ライブラリ

• ビット演算畳み込みの modint 用共通実装
• Bitwise Zeta / Möbius Transform
• modint998244353 の共通剰余演算
• Walsh–Hadamard Transform
• modint998244353

検証コード

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

コード

#ifndef BITWISE_CONVOLUTION_HPP
#define BITWISE_CONVOLUTION_HPP

#include "../components/bitwise_zeta.hpp"
#include "../components/walsh_hadamard.hpp"
#include "../components/bitwise_convolution_modular.hpp"
#include <type_traits>
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

namespace bitwise_convolution_detail {
template <int kind, class T>
std::vector<T> multiply(std::vector<T> a, std::vector<T> b) {
	if (a.empty() || b.empty()) return {};
	std::size_t n = std::bit_ceil(std::max(a.size(), b.size()));
	a.resize(n, T(0));
	b.resize(n, T(0));
#if (defined(__x86_64__) || defined(__i386__)) && !defined(BITWISE_CONVOLUTION_DISABLE_AVX2)
	if constexpr (std::is_same_v<T, mint>) {
		if (n >= 8 && Modular::vectorized()) {
			Modular::multiply<kind>(a, b);
			return a;
		}
	}
#endif
	if constexpr (kind == 2) {
		walsh_hadamard(a);
		walsh_hadamard(b);
	} else {
		bitwise_zeta<false, kind == 0>(a);
		bitwise_zeta<false, kind == 0>(b);
	}
	for (std::size_t i = 0; i < n; ++i) a[i] *= b[i];
	if constexpr (kind == 2) {
		walsh_hadamard(a);
		if constexpr (std::numeric_limits<T>::is_integer)
			for (T &x : a) x /= std::int64_t(n);
		else {
			T inverse = T(1) / T(n);
			for (T &x : a) x *= inverse;
		}
	} else bitwise_zeta<true, kind == 0>(a);
	return a;
}
}

template <class T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
	return bitwise_convolution_detail::multiply<0>(std::move(a), std::move(b));
}
template <class T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
	return bitwise_convolution_detail::multiply<1>(std::move(a), std::move(b));
}
template <class T>
std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) {
	return bitwise_convolution_detail::multiply<2>(std::move(a), std::move(b));
}

#endif

Back to top page