Convolution

It calculates $(+,\times)$ convolution. Given two arrays $a_0, a_1, \cdots, a_{N - 1}$ and $b_0, b_1, \cdots, b_{M - 1}$, it calculates the array $c$ of length $N + M - 1$, defined by

$$c_i = \sum_{j = 0}^i a_j b_{i - j}$$

convolution

(1) vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)
💻(2) vector<static_modint<m>> convolution<int m>(vector<static_modint<m>> a, vector<static_modint<m>> b)

It calculates the convolution in $\bmod m$. It returns an empty array if at least one of $a$ and $b$ are empty.

Constraints

Complexity

convolution_ll

vector<ll> convolution_ll(vector<ll> a, vector<ll> b)

It calculates the convolution. It returns an empty array if at least one of $a$ and $b$ are empty.

Constraints

Complexity

Examples

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_f

#include <atcoder/convolution> #include <atcoder/modint> #include <cstdio> using namespace std; using namespace atcoder; int main() { int n, m; scanf("%d %d", &n, &m); vector<long long> a(n), b(m); for (int i = 0; i < n; i++) { scanf("%lld", &(a[i])); } for (int i = 0; i < m; i++) { scanf("%lld", &(b[i])); } vector<long long> c = convolution(a, b); // or: vector<long long> c = convolution<998244353>(a, b); for (int i = 0; i < n + m - 1; i++) { printf("%lld ", c[i]); } printf("\n"); return 0; }

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_f

#include <atcoder/convolution> #include <atcoder/modint> #include <cstdio> using namespace std; using namespace atcoder; using mint = modint998244353; int main() { int n, m; scanf("%d %d", &n, &m); vector<mint> a(n), b(m); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); a[i] = x; } for (int i = 0; i < m; i++) { int x; scanf("%d", &x); b[i] = x; } auto c = convolution(a, b); for (int i = 0; i < n + m - 1; i++) { printf("%d ", c[i].val()); } printf("\n"); return 0; }