問題一覧 > 通常問題

No.1753 Don't cheat.

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : nok0 / テスター : zkou Kite_kuma
お気に入りにしたユーザー ProblemId : 6663 / 自分の提出
問題文最終更新日: 2021-11-19 21:39:02
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 323 (順位表) の他の問題:

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.
    1. 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.
    2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。