FFT and convolutions

Classes
struct	cplib::radix2_fft_root< T >
	\(2^n\)-th root of unity for radix-2 FFT. More...

Functions
template<typename ModInt >
void	cplib::convolve_any_modint_inplace (std::vector< ModInt > &a, const std::vector< ModInt > &b)
	In-place convolution with arbitrary modulus.
template<typename ModInt >
std::vector< ModInt >	cplib::convolve_any_modint (const std::vector< ModInt > &a, const std::vector< ModInt > &b)
	Returns the convolution of two arrays modulo an arbitrary integer.
template<typename T >
void	cplib::convolve_inplace2 (std::vector< T > &a, std::vector< T > &b)
	In-place convolution where both arrays are modified.
template<typename T >
void	cplib::convolve_inplace (std::vector< T > &a, const std::vector< T > &b)
	In-place convolution where one array is modified.
template<typename T >
std::vector< T >	cplib::convolve (const std::vector< T > &a, const std::vector< T > &b)
	Returns the convolution of two arrays.
template<typename RandomIt >
void	cplib::fft_inplace (RandomIt first, RandomIt last)
	In-place fast Fourier transform (FFT).
template<typename RandomIt >
void	cplib::ifft_inplace (RandomIt first, RandomIt last)
	In-place inverse fast Fourier transform (IFFT).
template<typename T >
void	cplib::fft_inplace (std::vector< T > &a)
	In-place fast Fourier transform (FFT).
template<typename T >
void	cplib::ifft_inplace (std::vector< T > &a)
	In-place inverse fast Fourier transform (IFFT).
template<typename T >
std::vector< T >	cplib::multiply_multivar_fps (const std::vector< T > &a, const std::vector< T > &b, const std::vector< std::size_t > &shape)
	Multiply two multivariate formal power series (FPS).

Detailed Description

Function Documentation

convolve()

template<typename T >

std::vector< T > cplib::convolve	(	const std::vector< T > &	a,
		const std::vector< T > &	b
	)

Returns the convolution of two arrays.

See also

convolve_inplace2() for details.

convolve_any_modint()

template<typename ModInt >

std::vector< ModInt > cplib::convolve_any_modint	(	const std::vector< ModInt > &	a,
		const std::vector< ModInt > &	b
	)

Returns the convolution of two arrays modulo an arbitrary integer.

See also

convolve_any_modint_inplace() for details.

convolve_any_modint_inplace()

template<typename ModInt >

void cplib::convolve_any_modint_inplace	(	std::vector< ModInt > &	a,
		const std::vector< ModInt > &	b
	)

In-place convolution with arbitrary modulus.

Using two 64-bit FFT-friendly prime moduli, it effectively computes convolution modulo a large number, \(M\approx 1.9\times 10^{37}\). When convolution modulo \(P\) is interpreted as convolution over \(\mathbb{N}\) followed by modulo, the intermediate value is at most \((P-1)^2\min\{N_1,N_2\}\), where \(N_1,N_2\) are the lengths of the two sequences. As long as this value is smaller than \(M\), computation modulo \(M\) gives the unique and correct result.

Typically in competitive programming, \(P\approx 10^9\) and \(N_1,N_2\lesssim 10^6\), so \(M\) only needs to be larger than \(10^{25}\) or so. Arbitrary modulus convolution is more commonly implemented as three 32-bit moduli, as they combined provide a sufficiently large \(M\). However, benchmark shows that two 64-bit moduli is about as fast as three 32-bit moduli on 64-bit platforms.

Template Parameters

ModInt

A modint type. The only requirements are operator+, opeartor*, and conversion from uint64_t.

convolve_inplace()

template<typename T >

void cplib::convolve_inplace	(	std::vector< T > &	a,
		const std::vector< T > &	b
	)

In-place convolution where one array is modified.

The convolution of a and b is stored in a.

See also

convolve_inplace2() for details

convolve_inplace2()

template<typename T >

void cplib::convolve_inplace2	(	std::vector< T > &	a,
		std::vector< T > &	b
	)

In-place convolution where both arrays are modified.

The convolution of a and b is stored in a, with length a.size() + b.size() - 1, unless at least one of the array is empty, in which case the output is empty as well. The result length must be no larger than the largest \(2^n\) for which T has \(2^n\)-th root of unity.

b is modified in an unspecified way. Use convolve_inplace() if b needs to be preserved for later use, or convolve() if both a and b need to be preserved.

Template Parameters

T	See fft_inplace() for requirements for T.

fft_inplace() [1/2]

template<typename RandomIt >

void cplib::fft_inplace	(	RandomIt	first,
		RandomIt	last
	)

In-place fast Fourier transform (FFT).

The input length must be a power of two. The output is in bit-reversed order.

Let the input length be \(2^L\), and T be std::iterator_traits<RandomIt>::value_type, then a specialization of radix2_fft_root must exist for T and must provide \(2^n\)-th root of unity for all \(0\leq n \leq L\).

Template Parameters

RandomIt

Random-access iterator type.

fft_inplace() [2/2]

template<typename T >

void cplib::fft_inplace

(

std::vector< T > &

a

)

In-place fast Fourier transform (FFT).

The input length must be a power of two. The output is in bit-reversed order.

Let the input length be \(2^L\), then a specialization of radix2_fft_root must exist for T and must provide \(2^n\)-th root of unity for all \(0\leq n \leq L\).

ifft_inplace() [1/2]

template<typename RandomIt >

void cplib::ifft_inplace	(	RandomIt	first,
		RandomIt	last
	)

In-place inverse fast Fourier transform (IFFT).

Exactly undoes fft_inplace(). The input length must be a power of two, and must be in bit-reversed order.

Let the input length be \(2^L\), and T be std::iterator_traits<RandomIt>::value_type, then a specialization of radix2_fft_root must exist for T and must provide \(2^n\)-th root of unity for all \(0\leq n \leq L\). In addition, the multiplicative inverse of \(2\) must exist in T.

Template Parameters

RandomIt

Random-access iterator type.

ifft_inplace() [2/2]

template<typename T >

void cplib::ifft_inplace

(

std::vector< T > &

a

)

In-place inverse fast Fourier transform (IFFT).

Exactly undoes fft_inplace(). The input length must be a power of two, and must be in bit-reversed order.

Let the input length be \(2^L\), then a specialization of radix2_fft_root must exist for T and must provide \(2^n\)-th root of unity for all \(0\leq n \leq L\). In addition, the multiplicative inverse of \(2\) must exist in T.

multiply_multivar_fps()

template<typename T >

std::vector< T > cplib::multiply_multivar_fps	(	const std::vector< T > &	a,
		const std::vector< T > &	b,
		const std::vector< std::size_t > &	shape
	)

Multiply two multivariate formal power series (FPS).

Returns the product of two multivariate FPSs, with both inputs and the output truncated to the same shape. Formally, this returns \(H\) where

\[ H(x_1,x_2,\dots,x_k)\equiv F(x_1,x_2,\dots,x_k)G(x_1,x_2,\dots,x_k)\pmod{(x_1^{n_1},x_2^{n_2},\dots ,x_k^{n_k})} \]

Coefficients of \(F,G,H\) are given as \(n_1\times n_2\times \dots\times n_k\) multi-dimensional arrays, but flattened into one dimension in row-major order. That is, the subscript for the coefficient of the term \(x_1^{i_1}x_2^{i_2}\dots x_k^{i_k}\) is \(i=i_1n_2n_3\dots n_k+i_2n_3\dots n_k+\dots+i_{k-1}n_k+i_k\). shape is simply the sequence \(\{n_1,n_2,\dots,n_k\}\).

Time complexity is \(O(kN\log N)\) where \(N=n_1n_2\dots n_k\), and space complexity is \(O(kN)\). The algorithm comes from https://rushcheyo.blog.uoj.ac/blog/6547 (Chinese).

Template Parameters

T	See fft_inplace() for requirements for T.