← 返回题目列表

Codeforces · 2034/F1

F1. 海亚姆皇家法令(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的唯一区别是 $$$k$$$ 的约束以及 $$$k$$$ 的总和。

在古波斯,聪明的商人兼数学家海亚姆正在用他珍贵的宝箱玩游戏,宝箱里有 $$$n$$$ 红宝石,每颗价值 $$$2$$$ 第纳尔,$$$m$$$ 蓝色蓝宝石,每颗价值 $$$1$$$ 第纳尔。他还有一个书包,一开始是空的,$$$k$$$ 滚动成对 $$$(r_1, b_1), (r_2, b_2), \ldots, (r_k, b_k)$$$ 描述特殊情况。

$$$n + m$$$ 轮的游戏进行如下:

1. 海亚姆从宝箱中均匀随机抽取一颗宝石。
2. 他从箱子中取出宝石并将其放入背包中。
3. 如果存在一个卷轴 $$$i$$$ ($$$1 \leq i \leq k$$$),并且箱子中正好包含 $$$r_i$$$ 红色红宝石和 $$$b_i$$$ 蓝色蓝宝石,Khayyam 会收到一项皇家法令,将其背包中所有宝石的价值加倍,作为实现特殊配置的奖励。

请注意,某些宝石的价值可能会受到多个法令的影响,在这种情况下,宝石的价值会翻倍多次。

确定游戏结束时海亚姆背包的预期价值,以 $$$998,244,353$$$ 为模。

正式地,让 $$$M = 998,244,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 500$$$) — 红宝石的数量、蓝色蓝宝石的数量和分别描述特殊情况的卷轴。

接下来的 $$$k$$$ 行包含两个整数 $$$r_i$$$、$$$b_i$$$ ($$$0 \leq r_i \leq n$$$、$$$0 \leq b_i \leq m$$$、$$$1 \leq r_i + b_i \leq n+m-1$$$)。保证 $$$(r_i, b_i)$$$ 是不同的。

保证所有测试用例的$$$n$$$总和和$$$m$$$总和不超过$$$2 \cdot 10^5$$$,并且所有测试用例的$$$k$$$总和不超过$$$500$$$。

输出

对于每个测试用例,打印一个整数:进程结束时 Khayyam 书包的预期值,以 $$$998,244,353$$$ 为模。

示例

输入 #1

5
3 4 0
1 1 1
1 0
3 3 2
1 1
2 2
3 3 2
2 1
1 2
10 4 5
1 0
8 0
6 4
0 2
7 4

输出 #1

10
499122180
798595498
149736666
414854846

注意

在第一个测试用例中,在流程结束时,总会有 $$$3$$$ 红色红宝石和 $$$4$$$ 蓝色蓝宝石。卷轴中描述的特殊条件均未满足,因此海亚姆挎包的价值保持不变。最后书包的总价值始终为 $$$2 \cdot 3 + 1 \cdot 4 = 10$$$。

在第二个测试用例中,考虑以下两种情况:

- 海亚姆以 $$$1/2$$$ 的概率抽到一颗红宝石,他的书包的价值变为 $$$2$$$。然后,他以 $$$1$$$ 的概率抽到一颗蓝色蓝宝石,他的书包的价值变为 $$$3$$$。
- 海亚姆以 $$$1/2$$$ 的概率抽出一颗蓝宝石,他的书包的价值变为 $$$1$$$。此时,宝箱中包含 $$$r_1 = 1$$$ 红色红宝石和 $$$b_1 = 0$$$ 蓝色蓝宝石,这与卷轴中描述的特殊情况相符​​。结果,书包的价值翻倍为 $$$2 \cdot 1 = 2$$$。然后,他以 $$$1$$$ 的概率抽到一颗红宝石,他的书包的价值变为 $$$4$$$。

因此,最后的预期值为 $$$\frac{1}{2} \cdot 3 + \frac{1}{2} \cdot 4 = \frac{7}{2}$$$,即 $$$499,122,180$$$ 模 $$$998,244,353$$$。