#PQJ402x3000. QOJ 402_3000
QOJ 402_3000
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试希望(hope) 希望(hope) 【题目背景】 我们所可以自慰的,想来想去,也还是所谓对于将来的希望。 希望是附丽于存在的,有存在,便有希望,有希望,便是光明。 【题目描述】 苏拉威西。距离地球进入木星洛希极限还有L 单位时间。 蔡德仁收到了来自艾莉芬的“点燃木星计划”。计划要求他将附近所有救援队召集 到同一台转向发动机处,清除障碍,并用“春节十二响”程序操纵发动机点燃木星。 转向发动机共有n 个,它们由n −1 条道路相连。任意两个转向发动机都可以通过 道路互相到达,二者的距离为其间最短路径的.边.数。 附近一共部署有k 支救援队s1, s2, . . . , sk,每一支救援队有一个救援范围。救援范 围是转向发动机集合的一个连通子集,其中任意两个发动机之间道路上的所有发动机 都在救援范围中。 我们称一个发动机u 可被救援范围为S 的救援队.到.达,当且仅当u 在S 中,且S 中任意一个发动机v 到u 的距离都.不.大.于L。这样,无论救援队身在岗位的何处,他 们都能在时间耗尽前抵达发动机u。 蔡德仁要指挥k 支救援队集中到同一台发动机处。但由于通讯中断,蔡德仁不知 道每支救援队的救援范围。他想计算出可行的调度方案数,于是将问题输入电脑。 在这台电脑的另一面——你,需要帮他统计出,在多少种可能的部署方案中存在一 台能被所有救援队到达的发动机。一个.方.案指一组救援范围{S 1, S 2, . . . , S k};两个方案 不同,当且仅当某个救援队si 在二者中的救援范围S i 不同。在这次联合政府规划的 饱和式救援中,两支队伍的救援范围可能.相.交甚至.相.同。 你知道,答案非常大。雪地车在成千上万个地标间穿梭,可能的救援范围浩如烟 海,集合所有队伍的方案却寥若晨星。但你没时间绝望,甚至没时间算出那个数字。 你只能算出答案对998244353 取模的结果。 那就是希望。 即便需要取模,也是光明。 【输入格式】 从文件hope.in 中读入数据。 第一行包含三个数n,L,k,依次表示转向发动机的个数,拯救地球剩余的时间, 和救援队的个数。 接下来n −1 行,每行两个整数u,v,表示第u 个和第v 个转向发动机之间有一条 道路相连。 第9 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试希望(hope) 【输出格式】 输出到文件hope.out 中。 仅一个整数,表示方案数对998244353 取模的结果。 【样例1 输入】 2 1 2 1 2 【样例1 输出】 7 【样例1 解释】 一共有以下几个可行的方案: 1 号救援队 2 号救援队 {1} {1} {1} {1,2} {2} {2} {2} {1,2} {1,2} {1} {1,2} {2} {1,2} {1,2} 【样例2 输入】 4 1 1 1 2 2 3 3 4 【样例2 输出】 9 第10 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试希望(hope) 【样例2 解释】 只有一个救援队,除了这个救援队的救援范围是全集{1,2,3,4} 之外的所有方案 都可行。 【样例3 输入】 5 1 1 1 2 1 3 2 4 2 5 【样例3 输出】 14 【样例4】 见选手目录下的hope/hope4.in 与hope/hope4.ans。 【样例4 解释】 这个测试点的图如下图所示: 【样例5】 见选手目录下的hope/hope5.in 与hope/hope5.ans。 第11 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试希望(hope) 【子任务】 测试点 n L k 是否为一条链 1 ≤16 ≤n = 1 否 2 ≤10 = 2 3 = n ≤10 4 ≤n 5 ≤500 = n 6 ≤103 ≤n = 1 7 ≤5 × 104 ≤30 ≤10 8 ≤105 ≤102 = 1 9 ≤10 10 ≤106 ≤n 是 11 ≤3 × 104 = n = 1 否 12 ≤4 × 104 ≤n 13 ≤5 × 104 ≤10 14 ≤105 = 1 15 ≤1.5 × 105 16 ≤2 × 105 = n ≤10 17 = 1 18 ≤n 19 ≤10 20 21 22 ≤106 = 1 23 ≤10 24 25 对于所有数据,有1 ≤n ≤106,0 ≤L ≤n,1 ≤k ≤10。 【提示】 .请.确.认.程.序.使.用.了.文.件.输.入.输.出、.没.有.输.出.多.余.调.试.信.息。 蔡德仁抬起头。那是他从未见过的景象——木星占据了大半个天空,绚丽的色彩透 过稀薄的大气,变得格外刺眼。 无边的海洋里漂流的小船,不知何时就会被狂风所倾覆;而小船上平凡的我们,也 只能怀着渺茫的希望,跟随着舵手指引的航向前行吧。 第12 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试希望(hope) 他走上前按下了Enter。 $ sudo ./spring12biubiu 指令已经发出。 第13 页 共13 页