問題一覧 > 通常問題

No.2876 Infection

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : 寝癖寝癖 / テスター : yuusaanyuusaan 👑 seekworserseekworser
2 ProblemId : 11064 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-06 21:50:51

問題文

寝癖くんは 全部で $N$ 人の人が参加するパーティに出席しました。

翌日、出席者のある一人がパーティ開始時に感染性のウイルスに罹っていたことが判明しました。

幸いなことにパーティ開始時にその人以外に感染者はいませんでしたが、

このウイルスには確率 $x\%$ で他人に感染する性質があるので、パーティ終了時までに直接間接を問わず

各出席者に感染してしまった可能性があります。なお、ウイルスの感染は独立に起こるものとします。

$N$ 人の出席者のうち、パーティ終了時にウイルスに感染していた人の人数の期待値を $\rm mod\ 998244353$ で求めてください。

より厳密な問題設定

より具体的には、次のようなイベントが発生します。

ウイルスに感染している人であって、以下の行動をまだ一度も行ったことのない人が存在する場合、そのような人を一人選び、以下の行動を行う。

  • 選んだ人間からまだウイルスに感染していない全ての人へ、それぞれ独立に確率 $x \%$ でウイルスを感染させる。

なお、パーティー終了時に感染している人数の期待値は、上記の操作で人を選ぶ順序によらないことが示せます。

入力

$N$ $x$
  • $1\le N\le 2500$
  • $0\le x\le100$
  • 入力はすべて整数

出力

感染者数の期待値 $\rm mod\ 998244353$ を一行で出力してください。

サンプル

サンプル1
入力
2 20
出力
598946613

$20\%$ の確率で感染者 $2$ 人、$80\%$ の確率で感染者 $1$ 人となるので、感染者数の期待値は $\frac{1}{5}\times2+\frac{4}{5}\times1=\frac{6}{5}$ 人です。

サンプル2
入力
3 90
出力
644865855
サンプル3
入力
7 0
出力
1

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