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

• $2 \leq m \leq 2 \times 10^9$
• $m$ is prime.
• There is an integer $c$ with $2^c | (m - 1)$ and $|a| + |b| - 1 \leq 2^c$.
• (1) T is int, uint, ll, or ull.

Complexity

• $O(n\log{n} + \log{\mathrm{mod}})$, where $n = |a| + |b|$.

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

• $|a| + |b| - 1 \leq 2^{24}$
• All the elements of the array are in ll after convolution

Complexity

• $O(n\log{n})$, where $n = |a| + |b|$.

Examples

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

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