問題一覧 > 通常問題

No.1751 Fortune Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : torisasami4torisasami4 / テスター : tokusakuraitokusakurai sapphire__15sapphire__15
9 ProblemId : 7250 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-06 15:22:35

問題文

$N$ 個の石の山と $1$ 枚のコインがあります。初め、$i\ (1 \le i \le N)$ 番目の山には $a_i$ 個の石が置いてあります。

これらを用いて、Alice と Bob の $2$ 人がゲームをします。 なお、コインを投げたとき、表と裏がそれぞれ $\large \frac{1}{2}$ の確率で出るものとします。

ゲームは Alice の手番 から始まり、手番のプレイヤーは以下の操作1~3を上から順に行います。


  1. 石が $1$ 個以上残っている山を $1$ つ選ぶ。選んだ山に $x$ 個の石が残っているとする。

  2. $1 \le k \le x$ を満たす整数 $k$ を $1$ つ宣言した後、コインを投げる。 表が出た場合、選んだ山から $k$ 個の石を取り除く。裏が出た場合、何も行わない。

  3. 操作2によって、全ての山に $1$ つも石が残っていない状態になった場合、手番のプレイヤーの勝利とし、ゲームを終了する。 そうでなければ、相手の手番に移る。


Alice も Bob も自分が勝つ確率が最大となるように行動するとき、Alice が勝つ確率を求めてください。

ただし、答えはある既約分数 $\large \frac{p}{q}$ として表わせて、$r \times q \equiv p\ (\textrm{mod}\ 998244353)$ かつ $0 \le r \lt 998244353$ を満たす整数 $r$ が一意に定まることが証明できるので、この $r$ を出力してください。

入力

$N$
$a_1\ a_2\ \ldots\ a_N$

【制約】

  • $1 \le N \le 2\times10^5$

  • $1 \le a_i \le 10^9$

  • 入力は全て整数

出力

答えを $\textrm{mod}\ 998244353$ で出力してください。

サンプル

サンプル1
入力
1
100
出力
665496236

両者はただ $1$ つの山の全ての石を取ろうとし、交互にコインを投げて先に表が出た方が勝ちます。 Alice が勝つ確率は $\large \frac{2}{3}$ です。

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

両者は常に石が残っている山を選び、$k=1$ を宣言することしかできません。 Alice が勝つ確率は $\large \frac{4}{9}$ です。

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