[AGC034F] RNG and XOR

给定 $n$ 和一个长度为 $2^n$ 的数组 $A$ (从 $0$ 标号). 有一个初始为 $0$ 的变量 $x$ . 不断操作, 每次操作以 $\dfrac {A_i}{\sum_{j=0}^{2^n-1} A_j}$ 的概率将 $x$ 变成 $x\oplus i$ . 对于所有 $i\in[0,2^n)$, 求出 $x$ 第一次变成 $i$ 的期望操作次数. $n\leqslant 18, 1\leqslant A\leqslant 1000$。

[problemUrl]: https://atcoder.jp/contests/agc034/tasks/agc034_f すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$ 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 $ にするために必要な操作の回数の期待値を求めてください。 ただし、期待値は mod $ 998244353 $ で出力してください。 より正確には、期待値が既約分数 $ P/Q $ で表されるとき、 $ R\ \times\ Q\ \equiv\ P\ \mod\ 998244353,\ 0\ \leq\ R\ <\ 998244353 $ を満たす整数 $ R $ が一意に定まるので、その $ R $ を出力してください。 なお、すべての $ i $ について、$ X $ を $ i $ にするために必要な操作の回数の期待値が有理数として存在し、 さらに mod $ 998244353 $ での整数表現が定義できることが問題の制約から証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_0 $ $ A_1 $ $ \cdots $ $ A_{2^N-1} $

$ 2^N $ 行出力せよ。 $ i+1 $ 行目 ($ 0\ \leq\ i\ \leq\ 2^N-1 $) には、$ X $ を $ i $ にするために必要な操作の回数の期待値を mod $ 998244353 $ で出力せよ。

2
1 1 1 1

0
4
4
4

2
1 2 1 2

0
499122180
4
499122180

4
337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355

0
468683018
635850749
96019779
657074071
24757563
745107950
665159588
551278361
143136064
557841197
185790407
988018173
247117461
129098626
789682908

### 制約 - $ 1\ \leq\ N\ \leq\ 18 $ - $ 1\ \leq\ A_i\ \leq\ 1000 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 $ 0 $ 回操作をした段階で $ X=0 $ なので、$ X $ を $ 0 $ にするのに必要な操作回数の期待値は $ 0 $ です。 また、どの状態から操作しても、操作後の $ X $ の値はそれぞれ $ 1/4 $ の確率で $ 0,1,2,3 $ になります。 よって、$ X $ を $ 1,2,3 $ にするのに必要な操作回数の期待値はいずれも $ 4 $ です。 ### Sample Explanation 2 $ X $ を $ 0,1,2,3 $ にするのに必要な操作回数の期待値は、それぞれ $ 0,7/2,4,7/2 $ です。