#PQJ393x2991. QOJ 393_2991
QOJ 393_2991
CCF NOI 2018 省队选拔赛 第一试秘密袭击(coat) 秘密袭击(coat) 【题目背景】 We could have had it all. . . . . . 我们本该,拥有一切 Counting on a tree. . . . . . 何至于此,数数树上 Counting on a Tree(CoaT)即是本题的英文名称。 【题目描述】 Access Globe 最近正在玩一款战略游戏。在游戏中,他操控的角色是一名C 国士 兵。他的任务就是服从指挥官的指令参加战斗,并在战斗中取胜。 C 国即将向D 国发动一场秘密袭击。作战计划是这样的:选择D 国的s 个城市, 派出C 国战绩最高的s 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度di, C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市,派遣战 绩第二高的士兵潜入所选择的城市中危险程度次高的城市,以此类推(即派遣战绩第i 高的士兵潜入所选择城市中危险程度第i 高的城市)。D 国有n 个城市,n −1 条双向道 路连接着这些城市,使得这些城市两两之间都可以互相到达。为了任务执行顺利,C 国 选出的s 个城市中,任意两个所选的城市,都可以不经过未被选择的城市互相到达。 Access Globe 操控的士兵的战绩是第k 高,他希望能估计出最终自己潜入的城市 的危险程度。Access Globe 假设C 国是以等概率选出任意满足条件的城市集合S ,他 希望你帮他求出所有可能的城市集合中,Access Globe 操控的士兵潜入城市的危险程 度之和。如果选择的城市不足k 个,那么Access Globe 不会被派出,这种情况下危险 程度为0。 当然,你并不想帮他解决这个问题,你也不打算告诉他这个值除以998, 244, 353 的 余数,你只打算告诉他这个值除以64,123 的余数。 【输入格式】 从文件coat.in 中读入数据。 第1 行包含3 个整数n、k、W,表示D 国城市的个数、Access Globe 所操控士兵 潜入的城市战绩排名以及D 国的所有城市中最大的危险程度; 第2 行包含n 个1 到W 之间的整数d1, d2, ..., dn,表示每个城市的危险程度; 第3 行到第n + 1 行,每行两个整数xi, yi,表示D 国存在一条连接城市xi 和城市 yi 的双向道路。 第7 页 共10 页
CCF NOI 2018 省队选拔赛 第一试秘密袭击(coat) 【输出格式】 输出到文件coat.out 中。 输出一个整数,表示所有可行的城市集合中,Access Globe 操控的士兵潜入城市的 危险程度之和除以64,123 的余数。 【样例1 输入】 5 3 3 2 1 1 2 3 1 2 2 3 1 4 1 5 【样例1 输出】 11 【样例1 解释】 D 国地图如下,其中危险程度为d 的城市的形状是(d + 3) 边形。 以下是所有符合条件且选择的城市不少于3 个的方案: • 选择城市1、2、3,Access Globe 的士兵潜入的城市危险程度为1; • 选择城市1、2、3、4,Access Globe 的士兵潜入的城市危险程度为1; • 选择城市1、2、3、5,Access Globe 的士兵潜入的城市危险程度为1; • 选择城市1、2、3、4、5,Access Globe 的士兵潜入的城市危险程度为2; • 选择城市1、2、4,Access Globe 的士兵潜入的城市危险程度为1; • 选择城市1、2、5,Access Globe 的士兵潜入的城市危险程度为1; 第8 页 共10 页
CCF NOI 2018 省队选拔赛 第一试秘密袭击(coat) • 选择城市1、2、4、5,Access Globe 的士兵潜入的城市危险程度为2; • 选择城市1、4、5,Access Globe 的士兵潜入的城市危险程度为2;而在选择的 城市少于3 时,Access Globe 的士兵潜入的城市危险程度均为0; 所以你应该输出(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) mod 64, 123 = 11。 【样例2 输入】 10 2 3 2 1 1 3 1 2 3 3 1 3 1 2 2 3 2 4 2 5 2 6 5 7 1 8 8 9 1 10 【样例2 输出】 435 第9 页 共10 页
CCF NOI 2018 省队选拔赛 第一试秘密袭击(coat) 【子任务】 测试点 n = k ≤ W = 地图是一条链 1 3 n 1,666 保证 2 15 不保证 3 20 4 300 10 保证 5 1,666 1,666 6 50 不保证 7 200 8 500 9 1,111 102 102 10 50 1,111 11 102 1,666 12 1,666 13 200 14 500 15 n 16 17 18 19 20 对于所有的数据,1 ≤k ≤n,,1 ≤di ≤W,n, k, W ≤1, 666。 第10 页 共10 页