| 197 | |
| 198 | template <class mint, internal::is_static_modint_t<mint>* = nullptr> |
| 199 | std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) { |
| 200 | int n = int(a.size()), m = int(b.size()); |
| 201 | int z = (int)internal::bit_ceil((unsigned int)(n + m - 1)); |
| 202 | a.resize(z); |
| 203 | internal::butterfly(a); |
| 204 | b.resize(z); |
| 205 | internal::butterfly(b); |
| 206 | for (int i = 0; i < z; i++) { |
| 207 | a[i] *= b[i]; |
| 208 | } |
| 209 | internal::butterfly_inv(a); |
| 210 | a.resize(n + m - 1); |
| 211 | mint iz = mint(z).inv(); |
| 212 | for (int i = 0; i < n + m - 1; i++) a[i] *= iz; |
| 213 | return a; |
| 214 | } |
| 215 | |
| 216 | } // namespace internal |
| 217 |
no test coverage detected