atcoder#ABC280E. [ABC280E] Critical Hit
[ABC280E] Critical Hit
Score : points
Problem Statement
There is a monster with initial stamina . Takahashi repeatedly attacks the monster while the monster's stamina remains or greater.
An attack by Takahashi reduces the monster's stamina by with probability and by with probability .
Find the expected value, modulo (see Notes), of the number of attacks before the monster's stamina becomes 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 by two coprime integers and , we can show that there exists a unique integer such that and . Print such .
Constraints
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Find the expected value, modulo , of the number of Takahashi's attacks.
3 10
229596204
An attack by Takahashi reduces the monster's stamina by with probability and by with probability .
- The monster's initial stamina is .
- After the first attack, the monster's stamina is with probability and with probability .
- After the second attack, the monster's stamina is with probability , with probability , and with probability . With probability , the stamina becomes or less, and Takahashi stops attacking after two attacks.
- If the stamina remains after two attacks, the monster's stamina always becomes 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 , print .
5 100
3
Takahashi's attack always reduces the monster's stamina by . After the second attack, the stamina remains , so the third one is required.
280 59
567484387