Detailed Description

template<typename T>
struct cplib::radix2_fft_root< T >

\(2^n\)-th root of unity for radix-2 FFT.

See also: radix2_fft_root<MMInt<998244353>>, radix2_fft_root<MMInt64<4512606826625236993>>, radix2_fft_root<std::complex<Float>>

Specialization of this class must provide a method static T get(int n) that returns the \(2^n\)-th root of unity. That is, \(\omega_{2^n}\) such that \(\omega_{2^n}^{2^n}=1\) but \(\omega_{2^n}^{2^{n-1}}\neq 1\), where \(1\) is the multiplicative identity. Specifically, for \(n=0\) we define \(\omega_{2^0}=1\).

Although \(\omega_{2^n}\) is generally not unique, the method must always return the same one for each \(n\). Additionally, for all \(n>0\) that \(\omega_{2^n}\) exists, \(\omega_{2^n}^2=\omega_{2^{n-1}}\) must hold.

The specialization can have undefined behavior if \(\omega_{2^n}\) doesn't exist.

Template Parameters

T	A commutative ring on which the \(2^n\)-th root of unity can be defined as above.

The documentation for this struct was generated from the following file:

src/cplib/conv/fft.hpp

cai_lw's competitive programming library