11283: [yosupo] Convolution - Multidimensional Convolution (Truncated)
[Creator : ]
Description
The polynomials in $K$ variables over $\mathbb{Z}/998244353\mathbb{Z}$, $f(x_1, x_2, ..., x_K)$ and $g(x_1, x_2, ..., x_K)$ are given.
Calculate a product of $f$ and $g$ with $\bmod (x_1^{N_1}, x_2^{N_2}, ..., x_K^{N_K})$.
Calculate a product of $f$ and $g$ with $\bmod (x_1^{N_1}, x_2^{N_2}, ..., x_K^{N_K})$.
Input
$K$
$N_1$ $N_2$ ... $N_K$
$f$
$g$
$f$, $g$ is the integer array of length $\prod N_i$ consisting of integers between $0$ and $998244352$.
$i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-th element is corresponded to the coefficient of the $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$.
$N_1$ $N_2$ ... $N_K$
$f$
$g$
$f$, $g$ is the integer array of length $\prod N_i$ consisting of integers between $0$ and $998244352$.
$i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-th element is corresponded to the coefficient of the $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$.
Output
$fg$
$fg$ is the integer array of length $\prod N_i$ consisting of integers between $0$ and $998244352$.
As the same with input format, $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-th element is corresponded to the coefficient of the $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$.
$fg$ is the integer array of length $\prod N_i$ consisting of integers between $0$ and $998244352$.
As the same with input format, $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$-th element is corresponded to the coefficient of the $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$.
Constraints
- $0 \leq K \leq 18$
- $\prod N_i \leq 2^{18}$
- $2 \leq N_i$
- $\prod N_i \leq 2^{18}$
- $2 \leq N_i$
Sample 1 Input
1
5
1 2 3 4 5
6 7 8 9 10
Sample 1 Output
6 19 40 70 110
Sample 2 Input
2
2 3
1 2 3 4 5 6
7 8 9 10 11 12
Sample 2 Output
7 22 30 80 73 182
Sample 3 Input
0
123
456
Sample 3 Output
56088