上海市大学生程序设计竞赛 - 十二月赛
单点时限: 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
499122177
10 30 2 3 3000 50 3000 10 4000 -10
838525257
提示
$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$