A7135. Khayyam's Royal Decree (Easy Version)
编程题
提高+/省选-
知识点
题目描述
这是本题的简单版本。两个版本的唯一区别在于 $k$ 和 $\sum k$ 的限制。
Khayyam 有一个**宝箱**，**宝箱**里初始有 $n$ 个红宝石和 $m$ 个蓝宝石。一个红宝石的价值为 $2$，一个蓝宝石的价值为 $1$。他还有一个**背包**，初始为空。另外，他还有 $k$ 张卷轴，第 $i$ 张卷轴上有数对 $(r_i,b_i)$。
Khayyam 将进行一个游戏，游戏共 $n+m$ 轮，每轮流程如下：
1. Khayyam 从**宝箱**中等概率随机拿出一个宝石。
2. 他将这个宝石放入**背包**中。
3. 若存在一张卷轴 $i$，使得**宝箱**中恰有 $r_i$ 个红宝石和 $b_i$ 个蓝宝石，将所有**背包**里的宝石的价值翻倍。
一个宝石的价值可以被多次翻倍。
求游戏结束时 Khayyam **背包**里宝石的价值总和的期望值，对 $998244353$ 取模。
Khayyam 有一个**宝箱**，**宝箱**里初始有 $n$ 个红宝石和 $m$ 个蓝宝石。一个红宝石的价值为 $2$，一个蓝宝石的价值为 $1$。他还有一个**背包**，初始为空。另外，他还有 $k$ 张卷轴，第 $i$ 张卷轴上有数对 $(r_i,b_i)$。
Khayyam 将进行一个游戏，游戏共 $n+m$ 轮，每轮流程如下：
1. Khayyam 从**宝箱**中等概率随机拿出一个宝石。
2. 他将这个宝石放入**背包**中。
3. 若存在一张卷轴 $i$，使得**宝箱**中恰有 $r_i$ 个红宝石和 $b_i$ 个蓝宝石，将所有**背包**里的宝石的价值翻倍。
一个宝石的价值可以被多次翻倍。
求游戏结束时 Khayyam **背包**里宝石的价值总和的期望值，对 $998244353$ 取模。
输入格式
多测，第一行一个整数 $T$ 表示数据组数。
每组数据的第一行三个整数 $n,m,k$。
接下来 $k$ 行，每行两个整数 $r_i,b_i$。
保证 $1\le T\le 500$，$1\le n,m,\sum n,\sum m\le 2\times 10^5$，$1\le k,\sum k\le 500$。
保证 $0\le r_i\le n$，$0\le b_i\le m$，$1\le r_i+b_i\le n+m-1$，且 $(r_i,b_i)$ 两两不同
每组数据的第一行三个整数 $n,m,k$。
接下来 $k$ 行，每行两个整数 $r_i,b_i$。
保证 $1\le T\le 500$，$1\le n,m,\sum n,\sum m\le 2\times 10^5$，$1\le k,\sum k\le 500$。
保证 $0\le r_i\le n$，$0\le b_i\le m$，$1\le r_i+b_i\le n+m-1$，且 $(r_i,b_i)$ 两两不同
输出格式
一行一个整数，表示答案对 $998244353$ 取模的值。
输入输出样例
输入 #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\times 3+1\times 4=10$。
对于第二组数据：
+ 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出红宝石再拿出蓝宝石，不会有卷轴被触发，总价值为 $3$；
+ 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出蓝宝石再拿出红宝石，卷轴 $1$ 会被触发，蓝宝石的价值翻倍，总价值为 $4$。
因此总价值的期望是 $\dfrac{1}{2}\times 3+\dfrac{1}{2}\times 4=\dfrac{7}{2}\equiv 499122180\pmod {998244353}$。
对于第二组数据：
+ 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出红宝石再拿出蓝宝石，不会有卷轴被触发，总价值为 $3$；
+ 有 $\dfrac{1}{2}$ 概率，Khayyam 先拿出蓝宝石再拿出红宝石，卷轴 $1$ 会被触发，蓝宝石的价值翻倍，总价值为 $4$。
因此总价值的期望是 $\dfrac{1}{2}\times 3+\dfrac{1}{2}\times 4=\dfrac{7}{2}\equiv 499122180\pmod {998244353}$。