No.2876 Infection
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 26
作問者 : 寝癖 / テスター : yuusaan 👑 seekworser
タグ : / 解いたユーザー数 26
作問者 : 寝癖 / テスター : yuusaan 👑 seekworser
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。