#P7844. 「dWoi R2」FFT / 狒狒贴

「dWoi R2」FFT / 狒狒贴

题目背景

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

题目描述

给定一个长度为 2n2^n 的非负整数序列 a0,a1,,a2n1a_0,a_1,\cdots,a_{2^n-1},请计算序列 A=DFTk(a)A=\text{DFT}^k(a)

其中 DFT(b)i\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} $$

输入格式

第一行两个非负整数 n,kn,k

接下来一行 2n2^n 个非负整数 a0,a1,,a2n1a_0,a_1,\cdots,a_{2^n-1}

输出格式

一行 2n2^n 个非负整数 A0,A1,,A2n1A_0,A_1,\cdots,A_{2^n-1}

3 3
1 2 3 4 5 6 7 8
288 831546728 224054051 383438562 998244321 614805727 774190238 166697561

提示

数据规模与约定

  • Subtask 1(10 pts):n11n\le 11k10k\le 10
  • Subtask 2(10 pts):k10k\le 10
  • Subtask 3(20 pts):n5n\le 5
  • Subtask 4(30 pts):n11n\le 11
  • Subtask 5(30 pts):无额外限制。

对于所有数据,1n171\le n\le 171k10181\le k\le10^{18}0ai9982443530\le a_i\le 998244353