NTT< mint > クラステンプレート

NTT Friendly 素数用 NTT 構造体 [詳解]

#include "fps2.hpp"

公開メンバ関数
void	setwy (int k)
	NTT ()
void	fft4 (vector< mint > &a, int k)
void	ifft4 (vector< mint > &a, int k)
void	ntt (vector< mint > &a)
void	intt (vector< mint > &a)
vector< mint >	multiply (const vector< mint > &a, const vector< mint > &b)
void	ntt_doubling (vector< mint > &a)
	NTT ()
vector< ll >	convolve (vector< ll > a, vector< ll > b)
	a, b の畳み込み mod M を求める

静的公開メンバ関数
static constexpr uint32_t	get_pr ()

公開変数類
mint	dw [level]
mint	dy [level]

静的公開変数類
static constexpr uint32_t	mod = mint::get_mod()
static constexpr uint32_t	pr = get_pr()
static constexpr int	level = __builtin_ctzll(mod - 1)

詳解

template<typename mint>
class NTT< mint >

NTT Friendly 素数用 NTT 構造体

fps2.hpp の 2 行目に定義があります。

構築子と解体子

NTT() [1/2]

template<typename mint>

NTT< mint >::NTT ( )

inline

fps2.hpp の 56 行目に定義があります。

参照先 level, setwy().

NTT() [2/2]

template<typename mint>

NTT< mint >::NTT ( )

inline

ntt.hpp の 32 行目に定義があります。

関数詳解

get_pr()

template<typename mint>

static constexpr uint32_t NTT< mint >::get_pr ( )

inlinestaticconstexpr

fps2.hpp の 3 行目に定義があります。

setwy()

template<typename mint>

void NTT< mint >::setwy ( int k )

inline

fps2.hpp の 43 行目に定義があります。

参照先 level.

fft4()

template<typename mint>

void NTT< mint >::fft4 ( vector< mint > & a, int k )

inline

fps2.hpp の 58 行目に定義があります。

ifft4()

template<typename mint>

void NTT< mint >::ifft4 ( vector< mint > & a, int k )

inline

fps2.hpp の 115 行目に定義があります。

ntt()

template<typename mint>

void NTT< mint >::ntt ( vector< mint > & a )

inline

fps2.hpp の 172 行目に定義があります。

intt()

template<typename mint>

void NTT< mint >::intt ( vector< mint > & a )

inline

fps2.hpp の 177 行目に定義があります。

multiply()

template<typename mint>

vector< mint > NTT< mint >::multiply ( const vector< mint > & a, const vector< mint > & b )

inline

fps2.hpp の 184 行目に定義があります。

参照先 setwy().

ntt_doubling()

template<typename mint>

void NTT< mint >::ntt_doubling ( vector< mint > & a )

inline

fps2.hpp の 213 行目に定義があります。

convolve()

template<typename mint>

vector< ll > NTT< mint >::convolve ( vector< ll > a, vector< ll > b )

inline

a, b の畳み込み mod M を求める

ntt.hpp の 46 行目に定義があります。

メンバ詳解

mod

template<typename mint>

uint32_t NTT< mint >::mod = mint::get_mod()

staticconstexpr

fps2.hpp の 38 行目に定義があります。

pr

template<typename mint>

uint32_t NTT< mint >::pr = get_pr()

staticconstexpr

fps2.hpp の 39 行目に定義があります。

level

template<typename mint>

int NTT< mint >::level = __builtin_ctzll(mod - 1)

staticconstexpr

fps2.hpp の 40 行目に定義があります。

dw

template<typename mint>

mint NTT< mint >::dw[level]

fps2.hpp の 41 行目に定義があります。

dy

template<typename mint>

mint NTT< mint >::dy[level]

fps2.hpp の 41 行目に定義があります。

---

このクラス詳解は次のファイルから抽出されました:

• math/fps2.hpp
• math/ntt.hpp