AT_agc034_f [AGC034F] RNG and XOR

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

N/A

N/A

### 制約 - $ 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 $ です。