cp-library

競技プログラミング用 C++ ライブラリ

View the Project on GitHub qandori/cp-library

:warning: 対称群上の畳み込み

convolution/symmetric_group_convolution.hpp · GitHub で見る

共通ページ

長さ \(n\) の全順列を添字とする配列の畳み込みを求めます。通常の加算や XOR の代わりに、順列の合成を用います。

\[c_p=\displaystyle\sum_{q\circ r=p}a_qb_r,\qquad(q\circ r)[i]=q[r[i]].\]

順列は 0, ..., n-1 を並べたものとし、配列は 辞書順に並べます。長さは \(n!\) です。合成は交換可能ではなく、一般に convolution(a, b) と convolution(b, a) は異なります。

#include "lib/convolution/symmetric_group_convolution.hpp"
#include <cassert>

std::vector<mint> a{1, 2};
std::vector<mint> b{3, 4};
auto c = symmetric_group_convolution(a, b);
assert((c == std::vector<mint>{11, 10}));

長さ 2 では順列は [0, 1] と [1, 0] の順です。前者は単位元、後者は自分自身との合成で単位元になります。一般の順列と添字の相互変換には 順列の辞書順順位・復元 を使えます。

操作 引数・返り値
symmetric_group_convolution(a, b) 同じ長さの const std::vector<Mint>& 2 本から std::vector<Mint> を返す。長さから n を決定
symmetric_group_convolution(fft, a, b) 構築済みの const SymmetricGroupFFT<Mint>& を使い、同じ畳み込みを返す

入力は変更しません。型 Mint は両配列で同じ modint 型とし、法は n より大きい素数を使います。mint・atcoder::modint998244353・atcoder::modint1000000007・動的 modint に対応します。整数からの構築・四則演算・単項マイナス・mod() を備える型を指定してください。動的 modint の法は fft の構築から使用終了まで変更しません。

\(0\le n\le10\) に対応します。空配列、長さが一致しない配列、長さが対応する階乗でない配列には std::invalid_argument を送出します。長さ 1 はスカラーの積を返します。これは空順列の群でも長さ 1 の順列の群でも同じ結果です。構築済み fft を渡す場合は、その size() と配列長を一致させます。

同じ次数で繰り返し計算するときは、変換の準備を共有できます。

#include "lib/convolution/symmetric_group_convolution.hpp"
#include <cassert>

SymmetricGroupFFT<> fft(3);
std::vector<mint> a{1, 2, 3, 4, 5, 6};
std::vector<mint> unit(6);
unit[0] = 1;
assert(symmetric_group_convolution(fft, a, unit) == a);
assert(symmetric_group_convolution(fft, unit, a) == a);

Maslen の対称群 Fourier 変換を使います。部分群への分割を Horner 型にまとめ、Young 図形の経路で中間計算を共有します。有限体上では平方根を必要としない有理的な Young の半正規表現を使います。Fourier 変換した各行列を順に掛け、転置アルゴリズムによる逆変換で係数に戻します。変換自体の API は 対称群 Fourier 変換 を参照してください。

参考: Library Checker issue #1432、David K. Maslen, The efficient computation of Fourier transforms on the symmetric group、同手法の FPSAC 1997 発表版。

\(n\) の分割 \(\lambda\) に対応する表現の次元を \(d_\lambda\) とすると、\(\displaystyle\sum_\lambda d_\lambda^2=n!\) です。畳み込みは前計算後 \(O\left(n^2n!+\displaystyle\sum_\lambda d_\lambda^3\right)\) 時間です。前計算・保持空間は Fourier 変換 と共通で、計算時の追加作業空間は \(O(n!)\) です。体の演算を \(O(1)\) とします。

依存ライブラリ

コード

#ifndef SYMMETRIC_GROUP_CONVOLUTION_HPP
#define SYMMETRIC_GROUP_CONVOLUTION_HPP

#include "../components/symmetric_group_fft.hpp"
#include "../components/matrix_arithmetic.hpp"
#include <stdexcept>
#include <vector>

template <class Mint>
std::vector<Mint> symmetric_group_convolution(const SymmetricGroupFFT<Mint> &fft, const std::vector<Mint> &a, const std::vector<Mint> &b) {
	auto x = fft.forward(a), y = fft.forward(b);
	for (const auto &block : fft.blocks()) {
		int d = block.dimension, offset = block.offset, length = d * d;
		std::vector<Mint> left(x.begin() + offset, x.begin() + offset + length);
		std::vector<Mint> right(y.begin() + offset, y.begin() + offset + length);
		auto product = matrix_detail::multiply(left, right, d, d, d);
		std::copy(product.begin(), product.end(), x.begin() + offset);
	}
	return fft.inverse(x);
}

template <class Mint>
std::vector<Mint> symmetric_group_convolution(const std::vector<Mint> &a, const std::vector<Mint> &b) {
	int n = 0, size = 1;
	while (std::size_t(size) < a.size() && n < 10) size *= ++n;
	if (a.size() != std::size_t(size) || b.size() != a.size()) throw std::invalid_argument("symmetric_group_convolution size");
	return symmetric_group_convolution(SymmetricGroupFFT<Mint>(n), a, b);
}

#endif
Back to top page