AT_agc034_f [AGC034F] RNG and XOR

すぬけ君得到了一个随机数生成器。这个随机数生成器会生成 $0$ 到 $2^N-1$ 之间的整数。每个整数被生成的概率由整数列 $A_0,A_1,\cdots,A_{2^N-1}$ 给出，整数 $i$（$0\leq i\leq 2^N-1$）被生成的概率为 $A_i/S$，其中 $S=\sum_{i=0}^{2^N-1}A_i$。此外，每次生成随机数都是独立进行的。 すぬけ君有一个整数 $X$。现在，$X=0$。すぬけ君可以进行任意多次如下操作： - 用随机数生成器生成一个整数 $v$，然后将 $X$ 替换为 $X\oplus v$。其中，$\oplus$ 表示按位异或运算。 请对于每个整数 $i$（$0\leq i\leq 2^N-1$），求出将 $X$ 变为 $i$ 所需操作次数的期望值。期望值需要对 $998244353$ 取模输出。更准确地说，若期望值为既约分数 $P/Q$，则输出满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R

输入以如下格式从标准输入读入。 > $N$ $A_0$ $A_1$ $\cdots$ $A_{2^N-1}$

输出 $2^N$ 行。第 $i+1$ 行（$0\leq i\leq 2^N-1$）输出将 $X$ 变为 $i$ 所需操作次数的期望值对 $998244353$ 取模后的结果。

## 限制条件 - $1\leq N\leq 18$ - $1\leq A_i\leq 1000$ - 输入的所有值均为整数。 ## 样例解释 1 操作 $0$ 次时 $X=0$，所以将 $X$ 变为 $0$ 所需操作次数的期望值为 $0$。另外，无论从哪个状态操作，操作后 $X$ 的值都以 $1/4$ 的概率变为 $0,1,2,3$。因此，将 $X$ 变为 $1,2,3$ 所需操作次数的期望值均为 $4$。 ## 样例解释 2 将 $X$ 变为 $0,1,2,3$ 所需操作次数的期望值分别为 $0,7/2,4,7/2$。 由 ChatGPT 4.1 翻译