MCPcopy Create free account
hub / github.com/atcoder/ac-library / convolution

Function convolution

atcoder/convolution.hpp:219–228  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

217
218template <class mint, internal::is_static_modint_t<mint>* = nullptr>
219std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {
220 int n = int(a.size()), m = int(b.size());
221 if (!n || !m) return {};
222
223 int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));
224 assert((mint::mod() - 1) % z == 0);
225
226 if (std::min(n, m) <= 60) return convolution_naive(std::move(a), std::move(b));
227 return internal::convolution_fft(std::move(a), std::move(b));
228}
229template <class mint, internal::is_static_modint_t<mint>* = nullptr>
230std::vector<mint> convolution(const std::vector<mint>& a,
231 const std::vector<mint>& b) {

Callers 5

mainFunction · 0.85
mainFunction · 0.85
CONV_same_lengthFunction · 0.85
CONV_long_emptyFunction · 0.85
TESTFunction · 0.85

Calls 5

bit_ceilFunction · 0.85
convolution_naiveFunction · 0.85
convolution_fftFunction · 0.85
sizeMethod · 0.45
valMethod · 0.45

Tested by 1

TESTFunction · 0.68