No.2876 Infection
タグ : / 解いたユーザー数 25
作問者 :
寝癖
/ テスター :
yuusaan
👑 
seekworser
Problem Statement
Neguse-kun attended a party with a total of $N$ participants.
The next day, it turned out that one of the attendees had been infected with a contagious virus at the start of the party.
Fortunately, no one else was infected at the start of the party, but
since this virus has the property of infecting other people with probability $x\%$, each attendee may have been infected, directly or indirectly,
by the end of the party. Infections are assumed to occur independently.
Find the expected number of people among the $N$ attendees who were infected with the virus at the end of the party, $\rm mod\ 998244353$.
More rigorous problem setting
More specifically, the following event takes place.
If there exists a person who is infected with the virus and has never yet performed the action below, choose one such person and perform the action below.
- From the chosen person, infect each person who is not yet infected with the virus, independently with probability $x \%$.
It can be shown that the expected number of people infected at the end of the party does not depend on the order in which people are chosen in the above operation.
Input
$N$ $x$
- $1\le N\le 2500$
- $0\le x\le100$
- All inputs are integers.
Output
Output the expected number of infected people, $\rm mod\ 998244353$, on one line.
Sample
Sample 1
Input
2 20
Output
598946613
With probability $20\%$ there are $2$ infected people, and with probability $80\%$ there is $1$ infected person, so the expected number of infected people is $\frac{1}{5}\times2+\frac{4}{5}\times1=\frac{6}{5}$.
Sample 2
Input
3 90
Output
644865855
Sample 3
Input
7 0
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。