畳み込みの型別振り分け

components/convolution_dispatch.hpp · GitHub で見る

共通ページ · 軽量実装なし

畳み込みと派生する畳み込みが共有する部品です。通常は convolution/convolution.hpp を読み込みます。

convolution(a,b) は同じ要素型の vector<T> を受け取り、積の係数を vector<T> で返します。空入力があれば空配列を返し、それ以外の長さは a.size()+b.size()-1 です。要素型ごとの利用条件は公開側の畳み込みと同じです。

法 998244353、その他の固定法 modint、整数、浮動小数点・複素数、その他の環に応じて演算を選択します。FPS のクラス自体は読み込みません。

出力長を \(N\) として、NTT・FFT を使う型では \(O(N\log N)\) 時間・\(O(N)\) 追加空間です。汎用の環では、入力長を \(n,m\) として \(O(nm)\) 時間・\(O(n+m)\) 出力空間です。

依存ライブラリ

• FFT
• FPS のブロック変換
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS の結果配列への一括変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• NTT（法指定）
• 実数・複素数の畳み込み
• 任意 mod・整数の畳み込み
• 一般の環の畳み込み
• modint998244353

検証コード

• test/convolution.test.cpp
• test/cyclic_convolution.test.cpp
• test/multiplicative_convolution.test.cpp
• test/multivariate_convolution.test.cpp
• test/ordered_convolution.test.cpp

コード

#ifndef CONVOLUTION_DISPATCH_HPP
#define CONVOLUTION_DISPATCH_HPP

#include <complex>
#include <limits>
#include <type_traits>
#include <vector>

#include "mint_convolution.hpp"
#include "../convolution/convolution_fft.hpp"
#include "../convolution/convolution_mod.hpp"
#include "../convolution/convolution_ring.hpp"

namespace convolution_detail {
template <class T>
struct IsComplex : std::false_type {};
template <class T>
struct IsComplex<std::complex<T>> : std::true_type {};
}

template <class T>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b) {
	if constexpr (requires { T::mod(); T::raw(0); a[0].val(); }) {
		if constexpr (T::mod() == 998244353) {
			if constexpr (std::is_same_v<T, mint>) return mint_convolution_detail::multiply(a, b);
			else {
				std::vector<mint> x(a.size()), y(&a == &b ? 0 : b.size());
				for (std::size_t i = 0; i < a.size(); ++i) x[i] = mint::raw(a[i].val());
				if (&a != &b) for (std::size_t i = 0; i < b.size(); ++i) y[i] = mint::raw(b[i].val());
				auto values = &a == &b ? mint_convolution_detail::multiply(x, x) : mint_convolution_detail::multiply(x, y);
				std::vector<T> result;
				result.reserve(values.size());
				for (auto x : values) result.push_back(T::raw(x.val()));
				return result;
			}
		} else {
			std::vector<std::uint32_t> x(a.size()), y(b.size());
			for (std::size_t i = 0; i < a.size(); ++i) x[i] = a[i].val();
			for (std::size_t i = 0; i < b.size(); ++i) y[i] = b[i].val();
			auto values = convolution_mod(x, y, T::mod());
			std::vector<T> result;
			result.reserve(values.size());
			for (auto x : values) result.push_back(T::raw(x));
			return result;
		}
	} else if constexpr (std::numeric_limits<T>::is_integer && sizeof(T) <= 8) return convolution_integer(a, b);
	else if constexpr (std::is_floating_point_v<T> || convolution_detail::IsComplex<T>::value) return convolution_fft(a, b);
	else return convolution_ring(a, b);
}

#endif

Back to top page