巡回・負巡回畳み込み（軽量実装）

convolution/cyclic_convolution_light.hpp · GitHub で見る

共通ページ · 軽量実装

巡回・負巡回畳み込みの高速実装はこちら

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

#include "lib/convolution/cyclic_convolution_light.hpp"

std::vector<long long> a{1, 2, 3}, b{4, 5};
auto c = light_convolution::cyclic_convolution(a, b, 3); // {19,13,22}
auto d = light_convolution::cyclic_convolution<true>(a, b, 3); // {-11,13,22}

操作	内容・返り値	計算量
light_convolution::cyclic_convolution(a,b,N)	積を \(x^N-1\) で割った余りの N 個の係数	\(O(\lvert a\rvert+\lvert b\rvert+M(N))\)
light_convolution::cyclic_convolution<true>(a,b,N)	積を \(x^N+1\) で割った余りの N 個の係数	\(O(\lvert a\rvert+\lvert b\rvert+M(N))\)

普通の積の係数 {4,13,22,15} にある \(15x^3\) は、N=3 の巡回版では定数項へ足し、負巡回版では定数項から引きます。出力は常に長さ N、入力は定数項から順に並べます。入力が N より長い場合も同じ規則で折り返します。

light_convolution::cyclic_convolution(a,b,N) は積を \(x^N-1\) で、<true> は \(x^N+1\) で割った余りを \(N\) 個の係数で返します。\(N > 0\) とし、係数型の条件は 通常の畳み込み と同じです。

通常の長さ \(N\) の畳み込み時間を \(M(N)\) として、時間 \(O(\lvert a\rvert+\lvert b\rvert+M(N))\)、追加空間 \(O(N)\) です。

依存ライブラリ

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

検証コード

• test/cyclic_convolution_light.test.cpp

コード

#ifndef CYCLIC_CONVOLUTION_LIGHT_HPP
#define CYCLIC_CONVOLUTION_LIGHT_HPP

#include <cassert>
#include <cstddef>
#include <vector>

#include "convolution_light.hpp"

namespace light_convolution {
template <bool negative = false, class T>
std::vector<T> cyclic_convolution(const std::vector<T> &a, const std::vector<T> &b, std::size_t n) {
	assert(n > 0);
	auto fold = [n](const std::vector<T> &v) {
		std::vector<T> result(n, T(0));
		for (std::size_t i = 0; i < v.size(); ++i) {
			if constexpr (negative) {
				if ((i / n) & 1) result[i % n] -= v[i];
				else result[i % n] += v[i];
			} else result[i % n] += v[i];
		}
		return result;
	};
	auto x = fold(a), y = fold(b);
	auto product = light_convolution::convolution(x, y);
	x.assign(n, T(0));
	for (std::size_t i = 0; i < product.size(); ++i) {
		if constexpr (negative) {
			if (i >= n) x[i - n] -= product[i];
			else x[i] += product[i];
		} else x[i % n] += product[i];
	}
	return x;
}

}

#endif

Back to top page