i < j 制約付き畳み込み（軽量実装）

convolution/ordered_convolution_light.hpp · GitHub で見る

共通ページ · 軽量実装

i < j 制約付き畳み込みの高速実装はこちら

light_convolution 名前空間で呼び出します。法 998244353 の計算は軽量 FPS を使い、通常の FPS は読み込みません。高速実装と同時に include できます。

#include "lib/convolution/ordered_convolution_light.hpp"

std::vector<mint> a{1, 2, 3}, b{4, 5, 6};
auto c = light_convolution::ordered_convolution(a, b); // {0,5,6,12,0}

操作	内容・返り値	計算量
light_convolution::ordered_convolution(a,b)	\(\displaystyle c_k=\sum_{i+j=k,\ i<j}a_ib_j\)	NTT・CRT・FFT: \(O(L\log^2 L)\)、一般の環: \(O(L^{\log_2 3})\)

a 側の添字が b 側の添字より小さい組だけを加えます。例では (i,j)=(0,1),(0,2),(1,2) の 3 組です。両入力が非空なら出力長は a.size()+b.size()-1、どちらかが空なら空配列です。入力は変更しません。

\(\displaystyle c_k = \sum_{\substack{i+j=k \\ i<j}} a_i b_j\)。係数型の条件は 通常の畳み込み と同じです。

\(L = \lvert a\rvert + \lvert b\rvert\) として、NTT・CRT・FFT では時間 \(O(L \log^{2} L)\)、一般の環では \(O(L^{\log_2 3})\)、追加空間はいずれも \(O(L)\) です。

依存ライブラリ

• FFT
• 軽量 FPS の NTT
• NTT（法指定）
• 実数・複素数の畳み込み
• 通常の畳み込み（軽量実装）
• 任意 mod・整数の畳み込み
• 一般の環の畳み込み
• modint998244353

検証コード

• test/ordered_convolution_light.test.cpp

コード

#ifndef ORDERED_CONVOLUTION_LIGHT_HPP
#define ORDERED_CONVOLUTION_LIGHT_HPP

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <vector>

#include "convolution_light.hpp"

namespace light_convolution {
template <class T>
std::vector<T> ordered_convolution(const std::vector<T> &a, const std::vector<T> &b) {
	if (a.empty() || b.empty()) return {};
	std::vector<T> result(a.size() + b.size() - 1, T(0));
	auto solve = [&](auto &&self, std::size_t l, std::size_t r) -> void {
		if (r - l <= 1 || l >= a.size() || l >= b.size()) return;
		if constexpr (std::is_same_v<T, mint>) {
			if (r - l <= 32) {
				for (std::size_t i = l; i < std::min(r, a.size()); ++i)
					for (std::size_t j = i + 1; j < std::min(r, b.size()); ++j) result[i + j] += a[i] * b[j];
				return;
			}
		}
		std::size_t mid = (l + r) / 2;
		if (mid < b.size()) {
			std::vector<T> x(a.begin() + l, a.begin() + std::min(mid, a.size()));
			std::vector<T> y(b.begin() + mid, b.begin() + std::min(r, b.size()));
			auto product = light_convolution::convolution(x, y);
			for (std::size_t i = 0; i < product.size(); ++i) result[l + mid + i] += product[i];
		}
		self(self, l, mid);
		self(self, mid, r);
	};
	solve(solve, 0, std::max(a.size(), b.size()));
	return result;
}

}

#endif

Back to top page