ntt998.hpp ファイル

#include "../../kyopro_library/template.hpp"
#include "../../kyopro_library/mod/modint.hpp"

[ソースコード]

関数
void	NTT998 (vector< Mod998 > &a, bool inv=false)
	数論変換
vector< Mod998 >	Convolve998 (vector< Mod998 > a, vector< Mod998 > b)
	AとBの畳み込み C[i] = Σ A[j]B[i-j] mod 998244353 を返す

関数詳解

NTT998()

void NTT998	(	vector< Mod998 > &	a,
		bool	inv = false )

数論変換

覚え書き

O(N log(N))

f(x) = Σ a[i]x^i, w^N = 1 とすると、F(t) = Σ f(w^i)t^i の各係数 mod 998244353 に変換する

ntt998.hpp の 7 行目に定義があります。

Convolve998()

vector< Mod998 > Convolve998	(	vector< Mod998 >	a,
		vector< Mod998 >	b )

AとBの畳み込み C[i] = Σ A[j]B[i-j] mod 998244353 を返す

覚え書き

O(N log(N))

注意

|a|+|b| <= 2^23 が必要

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