This documentation is automatically generated by online-judge-tools/verification-helper
#include "poly/convolution_naive.hpp"
#pragma once
template <class T, typename enable_if<!has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vector<T> ans(n + m - 1);
FOR(i, n) FOR(j, m) ans[i + j] += a[i] * b[j];
return ans;
}
template <class T, typename enable_if<has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vc<T> ans(n + m - 1);
if (n <= 16 && (T::get_mod() < (1 << 30))) {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u64 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = sm;
}
} else {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u128 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = T::raw(sm % T::get_mod());
}
}
return ans;
}
#line 2 "poly/convolution_naive.hpp"
template <class T, typename enable_if<!has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vector<T> ans(n + m - 1);
FOR(i, n) FOR(j, m) ans[i + j] += a[i] * b[j];
return ans;
}
template <class T, typename enable_if<has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vc<T> ans(n + m - 1);
if (n <= 16 && (T::get_mod() < (1 << 30))) {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u64 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = sm;
}
} else {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u128 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = T::raw(sm % T::get_mod());
}
}
return ans;
}