4556. KR-976

单点时限: 2.0 sec

内存限制: 512 MB

KR-976 loves mahjong, but it is especially hard to level up in maj-soul, so she begin to think when she will level up.

Now KR-976 simplifies and formalizes the problem and wants you to solve it:

In such a game, the player has $S$ points initially, and if her point may reach $T$,she will level up. Now she have $n$ rounds of the game to play. Each round may cause $m$ results. The $i$-th result will happen with probability $p_i$ and lead to $c_i$ points change.

Moreover, during the $n$ rounds:

  • If the player’s current points is less than or equal to 0, the player fails to level-up and can’t continue the rest rounds.

  • If the player’s current points is greater than or equal to $T$, the player will level up immediately and skip the rest games.

Now, your task is help the player to find the probability of level-up after at most $n$ rounds.

It is guaranteed the answer may be written by $p/q$, where $p,q$ are integers. To avoid precision of floating number, you should output an integer $x$ such as $0\le x<998244353, qx\equiv p\pmod {998244353}$.


The first line contains four integers $S、T、n、m$, representing the initial points, the aim points, the number of games and the number of results for each game respectively.

The next $m$ lines, each line contains two integers. The $(i+1)$-th line has two integers $w_i、c_i$, where $p_i=w_i/10000$ represents the probability of the $i$-th result and $c_i$ means the change of points.


Output a line, which contains an integer $p$.


10 20 1 2
5000 10
5000 -10
10 30 2 3
3000 50
3000 10
4000 -10


$0<S<T\leq 10000$

$0 < n \leq 10000,0 < m \leq 10$

$0< w_i\leq 10000, \sum w_i=10000$

$-10000\leq c_i\leq 10000,\gcd(c_1,…,c_m)\geq 10$

Where $\gcd$ means the greatest common divisor .

Sample 1 Explanation:

There is only one round.

The initial points is $10$.

The points needed to level up is $20$.

The player has 0.5 probability to make the point increase by $10$ (10+10=20, level-up!) and 0.5 probability to make it decrease by $10$ (10-10=0, failure!). So the answer is 0.5 , which is $499122177$ modulo $998244353$.

Sample 2 Explanation:

the probability is $0.3 + 0.3 * (0.3 + 0.3) = 0.48$

28 人解决,34 人已尝试。

38 份提交通过,共有 181 份提交。

4.6 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,6 月前.

最后提交: 11 月,1 周前.

来源: N/A