| 176 | |
| 177 | template <class mint, internal::is_static_modint_t<mint>* = nullptr> |
| 178 | std::vector<mint> convolution_naive(const std::vector<mint>& a, |
| 179 | const std::vector<mint>& b) { |
| 180 | int n = int(a.size()), m = int(b.size()); |
| 181 | std::vector<mint> ans(n + m - 1); |
| 182 | if (n < m) { |
| 183 | for (int j = 0; j < m; j++) { |
| 184 | for (int i = 0; i < n; i++) { |
| 185 | ans[i + j] += a[i] * b[j]; |
| 186 | } |
| 187 | } |
| 188 | } else { |
| 189 | for (int i = 0; i < n; i++) { |
| 190 | for (int j = 0; j < m; j++) { |
| 191 | ans[i + j] += a[i] * b[j]; |
| 192 | } |
| 193 | } |
| 194 | } |
| 195 | return ans; |
| 196 | } |
| 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) { |