/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 1600 点
問題文
すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、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 での整数表現が定義できることが問題の制約から証明できます。
制約
- 1 \leq N \leq 18
- 1 \leq A_i \leq 1000
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
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 で出力せよ。
入力例 1
2 1 1 1 1
出力例 1
0 4 4 4
0 回操作をした段階で X=0 なので、X を 0 にするのに必要な操作回数の期待値は 0 です。
また、どの状態から操作しても、操作後の X の値はそれぞれ 1/4 の確率で 0,1,2,3 になります。 よって、X を 1,2,3 にするのに必要な操作回数の期待値はいずれも 4 です。
入力例 2
2 1 2 1 2
出力例 2
0 499122180 4 499122180
X を 0,1,2,3 にするのに必要な操作回数の期待値は、それぞれ 0,7/2,4,7/2 です。
入力例 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
Score : 1600 points
Problem Statement
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.
Constraints
- 1 \leq N \leq 18
- 1 \leq A_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_0 A_1 \cdots A_{2^N-1}
Output
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.
Sample Input 1
2 1 1 1 1
Sample Output 1
0 4 4 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 Input 2
2 1 2 1 2
Sample Output 2
0 499122180 4 499122180
The expected numbers of operations until X becomes 0, 1, 2 and 3 are 0, 7/2, 4 and 7/2, respectively.
Sample Input 3
4 337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355
Sample Output 3
0 468683018 635850749 96019779 657074071 24757563 745107950 665159588 551278361 143136064 557841197 185790407 988018173 247117461 129098626 789682908