atcoder#ABC280E. [ABC280E] Critical Hit

[ABC280E] Critical Hit

Score : 500500 points

Problem Statement

There is a monster with initial stamina NN. Takahashi repeatedly attacks the monster while the monster's stamina remains 11 or greater.

An attack by Takahashi reduces the monster's stamina by 22 with probability P100\frac{P}{100} and by 11 with probability 1P1001-\frac{P}{100}.

Find the expected value, modulo 998244353998244353 (see Notes), of the number of attacks before the monster's stamina becomes 00 or less.

Notes

We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as PQ\frac{P}{Q} by two coprime integers PP and QQ, we can show that there exists a unique integer RR such that R×QP(mod998244353)R \times Q \equiv P\pmod{998244353} and 0R<9982443530 \leq R \lt 998244353. Print such RR.

Constraints

  • 1N2×1051 \leq N \leq 2\times 10^5
  • 0P1000 \leq P \leq 100
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN PP

Output

Find the expected value, modulo 998244353998244353, of the number of Takahashi's attacks.

3 10
229596204

An attack by Takahashi reduces the monster's stamina by 22 with probability 10100=110\frac{10}{100}=\frac{1}{10} and by 11 with probability 10010100=910\frac{100-10}{100}=\frac{9}{10}.

  • The monster's initial stamina is 33.
  • After the first attack, the monster's stamina is 22 with probability 910\frac{9}{10} and 11 with probability 110\frac{1}{10}.
  • After the second attack, the monster's stamina is 11 with probability 81100\frac{81}{100}, 00 with probability 18100\frac{18}{100}, and 1-1 with probability 1100\frac{1}{100}. With probability 18100+1100=19100\frac{18}{100}+\frac{1}{100}=\frac{19}{100}, the stamina becomes 00 or less, and Takahashi stops attacking after two attacks.
  • If the stamina remains 11 after two attacks, the monster's stamina always becomes 00 or less by the third attack, so he stops attacking after three attacks.

Therefore, the expected value is $2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100}$. Since 229596204×100281(mod998244353)229596204 \times 100 \equiv 281\pmod{998244353}, print 229596204229596204.

5 100
3

Takahashi's attack always reduces the monster's stamina by 22. After the second attack, the stamina remains 52×2=15-2\times 2=1, so the third one is required.

280 59
567484387