# [AGC034F] RNG and XOR

## 题目描述

[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.