問題一覧 > 通常問題

No.1289 RNG and OR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 28
作問者 : risujirohrisujiroh / テスター : pockynypockyny
9 ProblemId : 5025 / 出題時の順位表
問題文最終更新日: 2020-08-29 14:03:59

問題文

1回引くと $0$ 以上 $2^N-1$ 以下の整数がランダムに1つ手に入るガチャがあります.
それぞれの整数が手に入る確率は数列 $A$ によって表され,整数 $i$ が手に入る確率は $\frac{A_i}{S}$ です.
ただし,$S:=\sum_{i=0}^{2^N-1}A_i$ とします.
また,どの整数が手に入るかは毎回独立です.
今までに手に入れた整数全てのビットごとの論理和が初めて $2^N-1$ になるまでこのガチャを引き続けるとき,その回数の期待値を求めてください.
ただし,期待値が既約分数 $\frac{X}{Y}$ で表されるとき $X$ と $YZ$ が $998244353$ を法として合同となる $0$ 以上 $998244352$ 以下の整数 $Z$ を出力してください.
なお,この問題の制約下で期待値が有理数として存在し,上記の整数 $Z$ が一意に定まることが証明できます.

入力

$N$
$A_0\ A_1\ \cdots\ A_{2^N-1}$

  • $1 \leq N \leq 18$
  • $1 \leq A_i \leq 1000$
  • 入力は全て整数

出力

問題文中で定められた方法で期待値を出力してください.
最後に改行してください.

サンプル

サンプル1
入力
1
1 1
出力
2

$1$ が手に入るまでガチャを引き続けることになります.
$1$ が手に入る確率は $\frac{1}{2}$ なのでガチャを引く回数の期待値は $2$ です.

サンプル2
入力
2
5 2 2 1
出力
665496240

期待値は $\frac{14}{3}$ です.

サンプル3
入力
4
803 973 137 881 44 839 756 403 854 70 708 735 364 40 285 686
出力
284708662

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。