問題一覧 > 通常問題

No.1753 Don't cheat.

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma
1 ProblemId : 6663 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-19 21:39:02

問題文

AliceとBobが石取りゲームをすることを考えます。最初、山がいくつかあり、それぞれの山には $1$ 個以上の石があります。

ゲーム開始時に、チーターのBobは山を一つ選択しその山の石を全て取り除くことができます。この行動を行うかどうかは、Bobが任意に選択可能です。

その後、Aliceから始めて $2$ 人は交互に以下の操作を繰り返します。

  • 石が $1$ つ以上残っているような山を $1$ つ選ぶ。選んだ山に $X$ 個の石があるとき、 $1$ 個以上 $X$ 個以下の任意の個数の石をその山から取り除く。

先に操作ができなくなったプレイヤーが負けとなります。

さて、ゲームを始める前の初期状態を、以下の方法で生成します。

  • はじめ石の置かれた山は存在しない。
  • 以下のステップを行う。
    1. 整数 $i\in\left\{0,1,2,\dots,N\right\}$ をランダムに選ぶ。ただし $i$ が選ばれる確率は $\displaystyle\frac{A_i}{\sum_{i=0}^NA_i}$ であり、ステップごとの試行は独立である。
    2. もし $i$ が正の数だった場合、$i$ 個石が置かれた山を新たに追加し、ステップ $1$ に戻る。そうでないとき現在の状態を初期状態とし、ステップを終了する。

AliceもBobも自分が勝つために最適な行動をするとき、Aliceの勝率を求めてください。ただしAliceの勝率は有理数で表せることが証明可能なので、 $\bmod998244353$ で出力してください。

  • 有理数の $\bmod998244353$ 表記とは (クリックで展開します)
  • 有理数はある既約分数 $\frac{P}{Q}$ で表せます。更に $R×Q≡P(\mbox{mod } 998244353),\ 0 \le R< 998244353$ を満たす整数 $R$ が一意に定まることがこの問題の制約より証明できます。この $R$ を出力してください。

    制約

    • 入力は全て整数
    • $1 \le N\le 10^3$
    • $0 \le A_i \le 10^5$
    • $A_0 \ne 0$

    入力

    $N\ $
    $A_0$ $A_1$ $\dots$ $A_N$
    

    出力

    最後に改行してください。

    サンプル

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

    Aliceの勝率は $\frac{2}{15}$ です。

    サンプル2
    入力
    5
    27182 81828 45904 52353 60287 47135
    出力
    450579757

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