No.1289 RNG and OR
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
risujiroh
pockyny