P7844 "dWoi R2" FFT / Fefe Stickers

Gokuhara Gonta is trying to learn FFT...

Given a non-negative integer sequence $a_0, a_1, \cdots, a_{2^n-1}$ of length $2^n$, compute the sequence $A = \text{DFT}^k(a)$. Here, $\text{DFT}(b)_i$ is defined as: $$\text{DFT}(b)_i=\sum_{j=0}^{2^n-1}b_j\omega^{ij}\mod{998244353}$$ $$\omega\equiv3^{\frac{998244352}{2^n}}\pmod{998244353}$$

The first line contains two non-negative integers $n, k$. The next line contains $2^n$ non-negative integers $a_0, a_1, \cdots, a_{2^n-1}$.

Output one line with $2^n$ non-negative integers $A_0, A_1, \cdots, A_{2^n-1}$.

#### Constraints - Subtask 1 (10 pts): $n \le 11$ and $k \le 10$. - Subtask 2 (10 pts): $k \le 10$. - Subtask 3 (20 pts): $n \le 5$. - Subtask 4 (30 pts): $n \le 11$. - Subtask 5 (30 pts): no additional constraints. For all testdata, $1 \le n \le 17$, $1 \le k \le 10^{18}$, $0 \le a_i \le 998244353$. Translated by ChatGPT 5