問題一覧 > 通常問題

No.2876 Infection

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

問題文

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

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

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

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

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

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

より厳密な問題設定

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

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

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

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

入力

NN xx
  • 1N25001\le N\le 2500
  • 0x1000\le x\le100
  • 入力はすべて整数

出力

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

サンプル

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

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

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

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