P7844 「dWoi R2」FFT / 狒狒贴

题目背景

狱原权太正在尝试学习 FFT ……

题目描述

给定一个长度为 $2^n$ 的非负整数序列 $a_0,a_1,\cdots,a_{2^n-1}$,请计算序列 $A=\text{DFT}^k(a)$。 其中 $\text{DFT}(b)_i$ 定义为: $$\text{DFT}(b)_i=\sum_{j=0}^{2^n-1}b_j\omega^{ij}\mod{998244353}$$ $$\omega\equiv3^{\frac{998244352}{2^n}}\pmod{998244353}$$

输入格式

输出格式

说明/提示

#### 数据规模与约定 - Subtask 1(10 pts):$n\le 11$ 且 $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):无额外限制。 对于所有数据,$1\le n\le 17$,$1\le k\le10^{18}$,$0\le a_i\le 998244353$。