通常の畳み込み（軽量実装）

convolution/convolution_light.hpp · GitHub で見る

共通ページ · 軽量実装

通常の畳み込みの高速実装はこちら

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

#include "lib/convolution/convolution_light.hpp"

std::vector<mint> a{1, 2, 3}, b{4, 5};
auto c = light_convolution::convolution(a, b); // {4,13,22,15}

操作	内容・返り値	計算量
light_convolution::convolution(a,b)	通常の畳み込み \(\displaystyle c_k=\sum_{i+j=k}a_ib_j\) を返す。係数型から実装を選ぶ	NTT・CRT・FFT: \(O(L\log L)\)、一般の環: \(O(L^{\log_2 3})\)

\(\displaystyle c_k = \sum_{i+j=k} a_i b_j\) を返します。

配列は定数項から順に多項式の係数を並べます。例は \((1+2x+3x^2)(4+5x)\) の係数です。返り値は入力と同じ係数型の vector で、両方が非空なら長さは a.size()+b.size()-1、どちらかが空なら空配列です。入力は変更しません。mint の結果を整数に直すには c[i].val() を使います。

係数型	実装・条件
mint・mod 998244353 の modint	軽量 FPS の NTT。出力長 \(\le 2^{23}\)
その他の modint	32 bit 以下の mod。mod()・val()・raw() が必要。出力長 \(\le 2^{24}\)
64 bit 以下の整数	CRT による厳密計算。結果が係数型に収まること。出力長 \(\le 2^{24}\)
浮動小数点・std::complex	FFT による近似計算
その他の環	Karatsuba。T(0)・+=・-=・* が必要

各種畳み込みの参考記事。添字・集約・要素同士の演算は各ヘッダーの説明に記載しています。

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

依存ライブラリ

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

検証コード

• test/convolution_light.test.cpp
• test/cyclic_convolution_light.test.cpp
• test/multiplicative_convolution_light.test.cpp
• test/multivariate_convolution_light.test.cpp
• test/ordered_convolution_light.test.cpp

コード

#ifndef CONVOLUTION_LIGHT_HPP
#define CONVOLUTION_LIGHT_HPP

#include "../components/fps_light_ntt.hpp"
#include "convolution_fft.hpp"
#include "convolution_mod.hpp"
#include "convolution_ring.hpp"
#include <complex>
#include <limits>
#include <type_traits>
#include <vector>

namespace light_convolution {
namespace 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 (std::is_same_v<T, mint>) return fps_light_detail::multiply(a, b);
		using M = std::conditional_t<T::mod() == 998244353, mint, std::uint32_t>;
		auto convert = [](const std::vector<T> &input) {
			std::vector<M> result;
			result.reserve(input.size());
			for (auto x : input) {
				if constexpr (std::is_same_v<M, mint>) result.push_back(mint::raw(x.val()));
				else result.push_back(x.val());
			}
			return result;
		};
		auto x = convert(a), y = &a == &b ? std::vector<M>{} : convert(b);
		const auto &other = &a == &b ? x : y;
		auto values = [&] {
			if constexpr (std::is_same_v<M, mint>) return fps_light_detail::multiply(x, other);
			else return convolution_mod(x, other, T::mod());
		}();
		std::vector<T> result;
		result.reserve(values.size());
		for (auto value : values) {
			if constexpr (std::is_same_v<M, mint>) result.push_back(T::raw(value.val()));
			else result.push_back(T::raw(value));
		}
		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> || detail::IsComplex<T>::value) return convolution_fft(a, b);
	else return convolution_ring(a, b);
}
}

#endif

Back to top page