convolution_ll.hpp ファイル

#include "../../kyopro_library/template.hpp"
#include "../../kyopro_library/others/modcal.hpp"
#include "../../kyopro_library/math/ntt.hpp"

[ソースコード]

関数
ll	Garner (vector< ll > a, vector< ll > m, ll mod=INFL+3)
	x=ai mod mi を満たす x mod m を返す
template<int USE>
vector< ll >	ConvolveInt64 (vector< ll > a, vector< ll > b, ll mod=INFL+3)
	a, b の自然数での畳み込みを返す

関数詳解

Garner()

ll Garner	(	vector< ll >	a,
		vector< ll >	m,
		ll	mod = INFL+3 )

x=ai mod mi を満たす x mod m を返す

convolution_ll.hpp の 6 行目に定義があります。

ConvolveInt64()

template<int USE>

vector< ll > ConvolveInt64	(	vector< ll >	a,
		vector< ll >	b,
		ll	mod = INFL+3 )

a, b の自然数での畳み込みを返す

テンプレート引数

USE

使う素数の個数

USE=1 最終的な配列の値が X < 1224736769 = 1.2*10^9 = 2^30

USE=2 最終的な配列の値が X < 575334854091079681 = 5.8*10^17 = 2^59

USE=3 最終的な配列の値が X < 2^86

convolution_ll.hpp の 27 行目に定義があります。