[AGC034F] RNG and XOR

题意翻译

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

题目描述

[problemUrl]: https://agc034.contest.atcoder.jp/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 $ での整数表現が定義できることが問題の制約から証明できます。 Snuke found a random number generator. It generates an integer between $ 0 $ and $ 2^N-1 $ (inclusive). An integer sequence $ A_0,\ A_1,\ \cdots,\ A_{2^N-1} $ represents the probability that each of these integers is generated. The integer $ i $ ( $ 0\ \leq\ i\ \leq\ 2^N-1 $ ) is generated with probability $ A_i\ /\ S $ , where $ S\ =\ \sum_{i=0}^{2^N-1}\ A_i $ . The process of generating an integer is done independently each time the generator is executed. Snuke has an integer $ X $ , which is now $ 0 $ . He can perform the following operation any number of times: - Generate an integer $ v $ with the generator and replace $ X $ with $ X\ \oplus\ v $ , where $ \oplus $ denotes the bitwise XOR. For each integer $ i $ ( $ 0\ \leq\ i\ \leq\ 2^N-1 $ ), find the expected number of operations until $ X $ becomes $ i $ , and print it modulo $ 998244353 $ . More formally, represent the expected number of operations as an irreducible fraction $ P/Q $ . Then, there exists a unique integer $ R $ such that $ R\ \times\ Q\ \equiv\ P\ \mod\ 998244353,\ 0\ \leq\ R\ <\ 998244353 $ , so print this $ R $ . We can prove that, for every $ i $ , the expected number of operations until $ X $ becomes $ i $ is a finite rational number, and its integer representation modulo $ 998244353 $ can be defined.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ A_0 $ $ A_1 $ $ \cdots $ $ A_{2^N-1} $ ```

输出格式


Print $ 2^N $ lines. The $ (i+1) $ -th line ( $ 0\ \leq\ i\ \leq\ 2^N-1 $ ) should contain the expected number of operations until $ X $ becomes $ i $ , modulo $ 998244353 $ .

输入输出样例

输入样例 #1

2
1 1 1 1

输出样例 #1

0
4
4
4

输入样例 #2

2
1 2 1 2

输出样例 #2

0
499122180
4
499122180

输入样例 #3

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

输出样例 #3

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

输入样例 #4

2
1 1 1 1

输出样例 #4

0
4
4
4

输入样例 #5

2
1 2 1 2

输出样例 #5

0
499122180
4
499122180

输入样例 #6

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

输出样例 #6

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 $ - 入力される値はすべて整数である。 ### Constraints - $ 1\ \leq\ N\ \leq\ 18 $ - $ 1\ \leq\ A_i\ \leq\ 1000 $ - All values in input are integers. ### 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 $ です。 ### Sample Explanation 4 $ X=0 $ after zero operations, so the expected number of operations until $ X $ becomes $ 0 $ is $ 0 $ . Also, from any state, the value of $ X $ after one operation is $ 0 $ , $ 1 $ , $ 2 $ or $ 3 $ with equal probability. Thus, the expected numbers of operations until $ X $ becomes $ 1 $ , $ 2 $ and $ 3 $ are all $ 4 $ . ### Sample Explanation 5 The expected numbers of operations until $ X $ becomes $ 0 $ , $ 1 $ , $ 2 $ and $ 3 $ are $ 0 $ , $ 7/2 $ , $ 4 $ and $ 7/2 $ , respectively.