No.1753 Don't cheat.
Problem Statement
Consider Alice and Bob playing a stone-taking game. Initially, there are several piles, and each pile contains at least $1$ stone.
At the start of the game, Bob, who is a cheater, can choose one pile and remove all the stones from it. Bob may freely choose whether or not to perform this action.
After that, starting with Alice, the $2$ players alternately repeat the following operation.
- Choose $1$ pile that has at least $1$ stone remaining. If the chosen pile has $X$ stones, remove any number of stones between $1$ and $X$, inclusive, from that pile.
The player who first becomes unable to perform the operation loses.
Now, the initial state before the game starts is generated by the following method.
- Initially, there are no piles with stones.
- Perform the following steps.
- Choose an integer $i\in\left\{0,1,2,\dots,N\right\}$ at random. Here, the probability that $i$ is chosen is $\displaystyle\frac{A_i}{\sum_{i=0}^NA_i}$, and the trials at each step are independent.
- If $i$ is positive, add a new pile with $i$ stones and return to step $1$. Otherwise, take the current state as the initial state and end the steps.
Find the probability that Alice wins when both Alice and Bob act optimally to win. It can be proved that Alice's winning probability can be expressed as a rational number, so output it modulo $\bmod998244353$.
What the $\bmod998244353$ notation of a rational number means (click to expand)
A rational number can be expressed as an irreducible fraction $\frac{P}{Q}$. Furthermore, it can be proved from the constraints of this problem that an integer $R$ satisfying $R×Q≡P(\mbox{mod } 998244353),\
0 \le R< 998244353$ is uniquely determined. Output this $R$.Constraints
- All inputs are integers.
- $1 \le N\le 10^3$
- $0 \le A_i \le 10^5$
- $A_0 \ne 0$
Input
$N\ $ $A_0$ $A_1$ $\dots$ $A_N$
Output
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 1
Output
732045859
Alice's winning probability is $\frac{2}{15}$.
Sample 2
Input
5 27182 81828 45904 52353 60287 47135
Output
450579757
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nok0
Kite_kuma