#PQJ402x2998. QOJ 402_2998

    ID: 2950 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:十二省联合省选2019

QOJ 402_2998

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试皮配(mentor) 皮配(mentor) 【题目背景】 一年一度的综艺节目《中国好码农》又开始了。本季度,好码农由Yazid、Zayid、 小R、大R 四位梦想导师坐镇,他们都将组建自己的梦想战队,并率领队员向梦想发 起冲击。 四位导师的.派.系不尽相同,节目组为了营造看点,又将导师分成了不同的.阵.营,与 此同时对不同阵营、不同派系都作出了战队总人数限制: • 四位导师分成两个.阵.营: – Yazid、小R 两位导师组成.蓝.阵.营,他们两位的战队人数.总.和不得超过C0。 – Zayid、大R 两位导师组成.红.阵.营,他们两位的战队人数.总.和不得超过C1。 • 四位导师分成两个.派.系: – Yazid、Zayid 两位导师属于.鸭.派.系,他们两位的战队人数.总.和不得超过D0。 – 小R、大R 两位导师属于R .派.系,他们两位的战队人数.总.和不得超过D1。 【题目描述】 本季好码农邀请到了全国各路学生精英参赛。他们来自全国c 个城市的n 所不同 学校(城市的编号从1 至c,学校的编号从1 至n)。其中,第i 所学校所属的城市编 号为bi,且共有si 名选手参赛。 在【题目背景】中提到的各总人数限制之外,本季度《中国好码农》的导师选择阶 段有额外规则如下: • 来自同.城.市的所有选手必须加入相同的.阵.营。 • 来自同.学.校的所有选手必须选择相同的.导.师。 对于导师,大部分学校的学生对导师没有.偏.好。但是有k 所学校,其中每所学校的 学生有且仅有一位他们不喜欢的导师。同一所学校的学生不喜欢的导师相同,他们.不.会 .加.入.他.们.不.喜.欢.的.导.师.的.战.队。 面对琳琅满目的规则和选手的偏好,作为好码农忠实观众的你想计算出,在所有选 手都进行了战队选择后,战队组成共有多少种可能的局面? • 两种战队组成的局面被认为是不同的,当且仅当在存在一所学校,使得在这两种 局面中这所学校的选手加入了不同导师的战队。 • 由于答案可能很大,你只需输出可能局面数对998, 244, 353 取模的结果即可。 【输入格式】 从文件mentor.in 中读入数据。 第2 页 共13 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试皮配(mentor) 单个测试点中包含多组数据,输入的第一行包含一个非负整数T 表示数据组数。 接下来依次描述每组数据,对于每组数据: • 第1 行2 个正整数n, c,分别表示学校数目、城市数目。 • 第2 行4 个正整数C0,C1, D0, D1,分别表示题目中所描述的四个限制。 • 接下来n 行每行2 个正整数: – 这部分中第i 行的两个数依次为bi, si,分别表示第i 所学校的所属城市以 及选手数目。 – 保证bi ≤c,si ≤min{M, 10}。其中M = max {C0,C1, D0, D1}。 • 接下来1 行一个非负整数k,表示选手有偏好的学校数目。 • 接下来k 行,每行2 个整数i, p,描述编号为i 的学校选手有偏好: – 其中,p 为一个0 至3 之间的整数,描述该校选手不喜欢的导师:0 代表 Yazid,1 代表小R,2 代表Zayid,3 代表大R。 – 保证1 ≤i ≤n,且各行的i 互不相同。 对于输入的每一行,如果其包含多个数,则用单个空格将它们隔开。 【输出格式】 输出到文件mentor.out 中。 依次输出每组数据的答案,对于每组数据: • 一行一个整数,表示可能局面数对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 第3 页 共13 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试皮配(mentor) 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】 见选手目录下的mentor/mentor2.in 与mentor/mentor2.ans。 【样例3】 见选手目录下的mentor/mentor3.in 与mentor/mentor3.ans。 第4 页 共13 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试皮配(mentor) 【子任务】 测试点 n c k M 1 = 1 = n ≤1 = 1 2 = 10 ≤10 ≤100 3 = 20 = 0 4 = 30 5 ≤30 ≤500 6 = 500 = 0 ≤1000 7 = 30 = 30 8 = n 9 = 1000 = 0 ≤2500 10 = 30 其中,M = max {C0,C1, D0, D1}。 对于所有测试点,保证T ≤5。 对于所有测试点中的每一组数据,保证c ≤n ≤1000,k ≤30,M ≤2500, 1 ≤si ≤min{M, 10}。 .另.外,.请.你.注.意,.数.据.并.不.保.证.所.有.的c .个.城.市.都.有.参.赛.学.校。 【提示】 十二省联考命题组温馨提醒您: .数.据.千.万.条,.清.空.第.一.条。 .多.测.不.清.空,.爆.零.两.行.泪。 第5 页 共13 页