LCC/Moose '20 Contest 2 S4 - Gamer Alan

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Alan is playing his least favourite game "Liquidate, Create, Conquer" over the winter break. Of course, Alan hates playing this game, but his current rank is unsatisfactory so he keeps playing. This game has a very simple ELO system, where winning a game nets you 1 ELO point, while losing a game nets you -1 elo points. Alan's desired rank is K ELO points above his current ELO. Once he reaches this rank, he will immediately stop playing, but even if he doesn't reach this rank after N games he will give up. Given that Alan has probability p of winning each game, can you tell Alan the expected number of games he will play?

If you are unfamiliar with the concept of expected value, see here.

If you are unfamiliar with the concept of modular inverse, see here.

Input Specification

The only line of input contains 4 integers: N,K\ (1 \leq K \leq N \leq 10^6), a,b\ (1 \leq a \leq b \leq 10^9), \gcd(a,b)=1, p = \frac{a}{b}.

Output Specification

On one line, you are to output the expected number of games Alan will play. This value can be written as \frac{p}{q} where \gcd(p,q) = 1, you are to print p\cdot q^{-1}\pmod{998244353}


Subtask 1 (5%)

N \leq 10

Subtask 2 (10%)

N \leq 10^3

Subtask 3 (15%)

K = 1

Subtask 4 (20%)

A = B = 1

Subtask 5 (50%)

No further constraints.

Sample Input

2 1 1 2

Sample Output


Sample Explanation

There is a \frac{1}{2} chance that Alan wins his first game and ranks up. He plays 1 game.

There is a \frac{1}{2} chance that Alan loses his first game and thus plays a second game, after which he gives up. He plays 2 games.

E(wins) = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = \frac{3}{2}

3\cdot 2^{-1} \equiv 3\cdot 499122177 \equiv 499122178 \pmod{998244353}


There are no comments at the moment.