#2033. 「十二省联考2019」皮配

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

题目背景

一年一度的综艺节目《中国好码农》又开始了。本季度,好码农由 Yazid、Zayid、小 R、大 R 四位梦想导师坐镇,他们都将组建自己的梦想战队,并率领队员向梦想发起冲击。

四位导师的派系不尽相同,节目组为了营造看点,又将导师分成了不同的阵营,与此同时对不同阵营、不同派系都作出了战队总人数限制:

  • 四位导师分成两个阵营
    • Yazid、小 R 两位导师组成蓝阵营,他们两位的战队人数总和不得超过 C_0
    • Zayid、大 R 两位导师组成红阵营,他们两位的战队人数总和不得超过 C_1
  • 四位导师分成两个派系
    • Yazid、Zayid 两位导师属于鸭派系,他们两位的战队人数总和不得超过 D_0
    • 小 R、大 R 两位导师属于 R 派系,他们两位的战队人数总和不得超过 D_1

题目描述

本季好码农邀请到了全国各路学生精英参赛。他们来自全国 c 个城市的 n 所不同学校(城市的编号从 1 c ,学校的编号从 1 n )。其中,第 i 所学校所属的城市编号为 b_i ,且共有 s_i 名选手参赛。

在「题目背景」中提到的各总人数限制之外,本季度《中国好码农》的导师选择阶段有额外规则如下:

  • 来自同城市的所有选手必须加入相同的阵营
  • 来自同学校的所有选手必须选择相同的导师

对于导师,大部分学校的学生对导师没有偏好。但是有 k 所学校,其中每所学校的学生有且仅有一位他们不喜欢的导师。同一所学校的学生不喜欢的导师相同,他们不会加入他们不喜欢的导师的战队

面对琳琅满目的规则和选手的偏好,作为好码农忠实观众的你想计算出,在所有选手都进行了战队选择后,战队组成共有多少种可能的局面?

  • 两种战队组成的局面被认为是不同的,当且仅当在存在一所学校,使得在这两种局面中这所学校的选手加入了不同导师的战队。
  • 由于答案可能很大,你只需输出可能局面数对 998,244,353 取模的结果即可。

输入格式

从标准输入读入数据。

单个测试点中包含多组数据,输入的第一行包含一个非负整数 T 表示数据组数。接下来依次描述每组数据,对于每组数据:

  • 1 2 个正整数 n,c ,分别表示学校数目、城市数目。
  • 2 4 个正整数 C_0,C_1,D_0,D_1 ,分别表示题目中所描述的四个限制。
  • 接下来 n 行每行 2 个正整数:
    • 这部分中第 i 行的两个数依次为 b_i,s_i ,分别表示第 i 所学校的所属城市以及选手数目。
    • 保证 b_i \leq c s_i \leq \min\{M, 10\} 。其中 M=\max{\left\{ C_0,C_1,D_0,D_1\right\}}
  • 接下来 1 行一个非负整数 k ,表示选手有偏好的学校数目。
  • 接下来 k 行,每行 2 个整数 i,p ,描述编号为 i 的学校选手有偏好:
    • 其中, p 为一个 0 3 之间的整数,描述该校选手不喜欢的导师:0 代表 Yazid,1 代表小 R,2 代表 Zayid,3 代表大 R。
    • 保证 1\leq i\leq n ,且各行的 i 互不相同。

对于输入的每一行,如果其包含多个数,则用单个空格将它们隔开。

输出格式

输出到标准输出。

依次输出每组数据的答案,对于每组数据:

  • 一行一个整数,表示可能局面数对 998,244,353 取模的结果。

样例

样例输入 1

2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1

样例输出 1

1
22

样例说明 1

对于第 1 组数据:

  • 唯一的城市 1 包含共 3 名选手,但红阵营的总人数限制为 2 ,无法容纳这些选手,因此他们被迫只能选择蓝阵营。
  • 在此基础上,由于 1 号学校的选手不喜欢 Yazid 老师,因此他们就必须加入 R 派系的小 R 老师麾下。
  • 由于 R 派系总人数限制为 2 ,因此小 R 老师战队无法容纳 2 号学校的选手,所以他们只能被迫加入 Yazid 老师战队。
  • 综上所述,可能的局面仅有这一种。

对于第 2 组数据:

  • 一个显然的事实是,1 号城市的所有选手都无法加入蓝阵营,这是因为 1 号城市的选手总人数超过了蓝阵营的总人数限制,因此他们被迫全部加入红阵营。
  • 对于 2 号城市选手加入蓝阵营的情况,稍加计算可得出共有 15 种可能的局面。
  • 对于 2 号城市选手加入红阵营的情况,稍加计算可得出共有 7 种可能的局面。
  • 综上所述,可能的局面数为 15+7=22 种。

样例 2

见附加文件中的 2.in2.ans

样例 3

见附加文件中的 3.in3.ans

数据范围与提示

测试点 n c k M
1 =1 =n \le 1 =1
2 =10 \le 10 \le 100
3 =20 =0
4 =30
5 \le 30 \le 500
6 =500 =0 \le 1000
7 =30 = 30
8 =n
9 =1000 =0 \le 2500
10 =30

其中, M=\max{\left\{ C_0,C_1,D_0,D_1\right\}}

对于所有测试点,保证 T\leq 5

对于所有测试点中的每一组数据,保证 c\leq n\leq 1000 k\leq 30 M\leq 2500 1\leq s_i \leq \min\{M, 10\}

另外,请你注意,数据并不保证所有的 c 个城市都有参赛学校。

提示

十二省联考命题组温馨提醒您:

数据千万条,清空第一条。

多测不清空,爆零两行泪。