1259: #555. 「LibreOJ Round #8」Moejy0viiiiiv's Red Envelopes / 抢红包
Description
Moejy0viiiiiv 在平面直角坐标系上抢红包。从 (0,0)(0,0)(0,0) 出发，每天中午有 A/1996488707A/1996488707A/1996488707 的概率向上走一格，有 B/1996488707B/1996488707B/1996488707 的概率向右走一格，有 1−A/1996488707−B/19964887071-A/1996488707-B/19964887071−A/1996488707−B/1996488707 的概率立即停止行动（之后也不再行动），三种事件两两不会同时发生；Moejy0viiiiiv 在第 NNN 天傍晚离开平面直角坐标系（总共至多走 NNN 格）。
已知一个常数 DDD，在所有 (xD,yD)(0≤x,y)(xD, yD)(0 \leq x, y)(xD,yD)(0≤x,y) 处有一个红包；还有 KKK 个坑，分别在 (x1,y1),(x2,y2),(x3,y3),⋯,(xK,yK)(x_1, y_1), (x_2, y_2), (x_3, y_3), \cdots, (x_K, y_K)(x1,y1),(x2,y2),(x3,y3),⋯,(xK,yK)，走入坑中将在接下来的回合中无法行动。
Moejy0viiiiiv 会抢走所有她经过的红包（包含 (0,0)(0,0)(0,0)）问最终期望抢到的红包数量，输出这个值 mod998244353，注意 1996488707mod998244353=1。
Moejy0viiiiiv is collecting red envelopes on a rectangular plane. She starts at (0,0)(0,0)(0,0). Every day at noon, she walks from (x,y)(x, y)(x,y) to (x,y+1)(x,y+1)(x,y+1) with probability A/1996488707A/1996488707A/1996488707, and to (x+1,y)(x+1,y)(x+1,y) with probability B/1996488707B/1996488707B/1996488707, and stops immediately with probability 1−A/1996488707−B/19964887071-A/1996488707-B/19964887071−A/1996488707−B/1996488707 (once she stops, she will never move again). Besides, she also stops after walking for NNN days.
With a given constant integer DDD, there’s a red envelope at each (xD,yD)(0≤x,y)(xD, yD)(0 \leq x, y)(xD,yD)(0≤x,y). There’re also KKK barriers at (x1,y1),(x2,y2),(x3,y3),...,(xK,yK)(x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_K, y_K)(x1,y1),(x2,y2),(x3,y3),...,(xK,yK) (barriers never coincide with red envelopes). If she walks to a barrier, she will stop immediately.
Moejy0viiiiiv will collect each red envelope she passes by (including (0,0)(0,0)(0,0)). What’s the expected number of red envelopes Moejy0viiiiiv collects after NNN days? Output the answer mod998244353. Notice that 1996488707mod998244353=1.
输入格式
第一行两个整数 A,BA, BA,B。
第二行四个整数 N,D,M,KN, D, M, KN,D,M,K。
接下来 KKK 行，每行两个整数，第 i+2i + 2i+2 行两个数为 xi,yix_i, y_ixi,yi。
The first line contains two positive integers A,BA,BA,B.
The second line contains four positive integers N,D,M,KN,D,M,KN,D,M,K.
The following KKK lines each contains two integers, the i+2i+2i+2-th line contains xi,yix_i,y_ixi,yi.
输出格式
一行一个数，表示期望抢的红包数量。
Output contains one integer, the expected number of red envelopes mod998244353.
样例
样例输入1
1 1
2 2 5 1
1 0样例输出 1
2样例解释 1
共有 33 3个地方有红包，(0,0),(0,2),(2,0)(0, 0), (0, 2), (2, 0)(0,0),(0,2),(2,0)。 由于 (1,0)(1, 0)(1,0) 处是坑，所以无法抢 (2,0)(2, 0)(2,0) 处的红包，而抢到其余两处红包的概率均为 111。
注意，在本题中 A+BA+BA+B 不必为 111。
样例输入 2
1 2
2 2 5 0样例输出 2
6Sample Input 1
1 1
2 2 5 1
1 0Sample Output 1
2Sample Explanation 1
There’re three red envelopes satisfies x+y≤Nx+y\le Nx+y≤N, (0,0),(0,2),(2,0)(0, 0), (0, 2), (2, 0)(0,0),(0,2),(2,0). As there’s a barrier at (1,0)(1, 0)(1,0), the red envelope at (2,0)(2, 0)(2,0) is unreachable. The probability of getting the other two red envelopes are both 111.
A+BA+BA+B doesn’t need to be 111.
Sample Input 2
1 2
2 2 5 0Sample Output 2
6数据范围与提示
对于所有数据，1≤N≤1018,0≤K≤50,1≤D,M≤1000,0≤x1,x2,...,xK≤M1 \leq N \leq 10^{18}, 0 \leq K \leq 50, 1 \leq D, M \leq 1000, 0 \leq x_1, x_2, ..., x_K \leq M1≤N≤1018,0≤K≤50,1≤D,M≤1000,0≤x1,x2,...,xK≤M， ∀i∈{1,2,3,...,K},D∤xi∨D∤yi,xi+yi≤N,0≤A,B<998244353\forall i \in \{1, 2, 3, ..., K\}, D \nmid x_i \vee D \nmid y_i, x_i + y_i \leq N, 0 \leq A, B < 998244353∀i∈{1,2,3,...,K},D∤xi∨D∤yi,xi+yi≤N,0≤A,B<998244353。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值（百分比） | NNN | DDD | MMM | KKK |
|---|---|---|---|---|---|
| 111 | 999 | ≤104\le 10^4≤104 | - | - | - |
| 222 | 121212 | ≤105\le 10^5≤105 | ≤10\le 10≤10 | ≤10\le 10≤10 | 000 |
| 333 | 272727 | - | - | - | 000 |
| 444 | 888 | ≤105\le 10^5≤105 | ≤10\le 10≤10 | ≤10\le 10≤10 | - |
| 555 | 444444 | - | - | - | - |
For all test cases, 1≤N≤1018,0≤K≤50,1≤D,M≤1000,0≤x1,x2,...,xK≤M1 \leq N \leq 10^{18}, 0 \leq K \leq 50, 1 \leq D, M \leq 1000, 0 \leq x_1, x_2, ..., x_K \leq M1≤N≤1018,0