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
#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;
}
#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;
}