問題一覧 > 通常問題

No.1289 RNG and OR

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 40
作問者 : risujiroh / テスター : pockyny
お気に入りにしたユーザー ProblemId : 5025 / 自分の提出
問題文最終更新日: 2020-08-29 14:03:59
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 274 (順位表) の他の問題:

Problem Statement

There is a gacha that gives you one random integer between $0$ and $2^N-1$, inclusive, each time you draw it.
The probability of obtaining each integer is represented by a sequence $A$: the probability of obtaining the integer $i$ is $\frac{A_i}{S}$.
Here, let $S:=\sum_{i=0}^{2^N-1}A_i$.
Also, which integer is obtained is independent for each draw.
Suppose you keep drawing this gacha until the bitwise OR of all integers obtained so far becomes $2^N-1$ for the first time. Find the expected value of the number of draws.
Here, when the expected value is represented as an irreducible fraction $\frac{X}{Y}$, output the integer $Z$ between $0$ and $998244352$, inclusive, such that $X$ and $YZ$ are congruent modulo $998244353$.
It can be proved that, under the constraints of this problem, the expected value exists as a rational number and the integer $Z$ above is uniquely determined.

Input

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

  • $1 \leq N \leq 18$
  • $1 \leq A_i \leq 1000$
  • All inputs are integers.

Output

Output the expected value in the manner specified in the problem statement.
Print a newline at the end.

Sample

Sample 1
Input
1
1 1
Output
2

You keep drawing the gacha until you obtain $1$.
The probability of obtaining $1$ is $\frac{1}{2}$, so the expected number of draws is $2$.

Sample 2
Input
2
5 2 2 1
Output
665496240

The expected value is $\frac{14}{3}$.

Sample 3
Input
4
803 973 137 881 44 839 756 403 854 70 708 735 364 40 285 686
Output
284708662

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