max-min・min-max 畳み込み（高速版）

convolution/max_min_convolution.hpp · GitHub で見る

全体サイト（256 KiB向け） · 高速実装

軽量実装（64 KiB）はこちら

#include "lib/convolution/max_min_convolution.hpp"

std::vector<long long> a{3, 1, 4}, b{2, 5};
auto c = max_min_convolution(a, b); // {2,3,2,4}
auto d = min_max_convolution(a, b); // {3,2,4,5}

操作	内容・返り値	計算量
max_min_convolution(a,b)	\(\displaystyle c_k=\max_{i+j=k}\min(a_i,b_j)\)	\(\displaystyle O(L\sqrt{L\log L})\)
min_max_convolution(a,b)	\(\displaystyle c_k=\min_{i+j=k}\max(a_i,b_j)\)	\(\displaystyle O(L\sqrt{L\log L})\)

例えば c[1] は max(min(a[0],b[1]),min(a[1],b[0])) = 3 です。返り値は入力と同じ型の配列で、両方が非空なら長さは a.size()+b.size()-1、どちらかが空なら空配列です。入力は変更しません。

max_min_convolution は \(\displaystyle \max_{i+j=k} \min(a_i,b_j)\)、min_max_convolution は \(\displaystyle \min_{i+j=k} \max(a_i,b_j)\) を計算します。係数には大小比較できる型を使えます。出力長は \(2^{23}\) 以下です。

\(L = \lvert a\rvert + \lvert b\rvert\) として、時間 \(\displaystyle O(L \sqrt{L \log L})\)、追加空間 \(O(L)\) です。

依存ライブラリ

• FPS のブロック変換
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS と多項式除算の内部変換
• FPS の指数・冪の内部変換
• FPS の一点評価
• FPS 逆数のブロック変換
• FPS の内部演算
• FPS の結果配列への一括変換
• 疎 FPS の共通演算
• 疎 FPS の次数圧縮・前処理
• 疎 FPS の項収集・演算種別
• FPS 平方根のブロック変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• 形式的冪級数（高速版）
• modint998244353

コード

#ifndef MAX_MIN_CONVOLUTION_HPP
#define MAX_MIN_CONVOLUTION_HPP

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <functional>
#include <numeric>
#include <vector>

#include "../fps/fps.hpp"

namespace max_min_convolution_detail {
template <class T, class Compare>
std::vector<T> multiply(const std::vector<T> &a, const std::vector<T> &b, Compare compare) {
	if (a.empty() || b.empty()) return {};
	assert(a.size() + b.size() - 1 <= std::size_t(1) << 23);
	int n = a.size(), m = b.size(), length = n + m - 1;
	std::vector<T> result(length, a[0]);
	std::vector<std::uint8_t> done(length);
	if (std::min(n, m) <= 32) {
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j) {
				T value = compare(a[i], b[j]) ? b[j] : a[i];
				if (!done[i + j] || compare(value, result[i + j])) result[i + j] = value;
				done[i + j] = 1;
			}
		return result;
	}
	std::vector<int> order(n + m), pending;
	std::iota(order.begin(), order.end(), 0);
	auto value = [&](int i) -> decltype(auto) { return i < n ? a[i] : b[i - n]; };
	std::sort(order.begin(), order.end(), [&](int i, int j) { return compare(value(i), value(j)); });
	int block = std::max(1, int(std::sqrt(double(n + m) * std::log2(n + m))));
	fps active_a(n), active_b(m);
	int remaining = length;
	for (int first = 0; first < n + m && remaining; first += block) {
		int last = std::min(n + m, first + block);
		fps x = active_a, y = active_b;
		for (int k = first; k < last; ++k) {
			int i = order[k];
			if (i < n) x[i] = 1;
			else y[i - n] = 1;
		}
		auto counts = x * y;
		pending.clear();
		for (int k = 0; k < length; ++k)
			if (!done[k] && counts[k] != mint(0)) pending.push_back(k);
		for (int k = first; k < last; ++k) {
			int i = order[k];
			for (int pos : pending) {
				if (done[pos]) continue;
				int j = pos - (i < n ? i : i - n);
				bool exists = i < n ? 0 <= j && j < m && active_b[j] != mint(0) : 0 <= j && j < n && active_a[j] != mint(0);
				if (exists) result[pos] = value(i), done[pos] = 1, --remaining;
			}
			if (i < n) active_a[i] = 1;
			else active_b[i - n] = 1;
		}
	}
	return result;
}
}

template <class T>
std::vector<T> max_min_convolution(const std::vector<T> &a, const std::vector<T> &b) {
	return max_min_convolution_detail::multiply(a, b, std::greater<T>{});
}
template <class T>
std::vector<T> min_max_convolution(const std::vector<T> &a, const std::vector<T> &b) {
	return max_min_convolution_detail::multiply(a, b, std::less<T>{});
}

#endif

Back to top page