序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
---|
题目背景
我们所可以自慰的,想来想去,也还是所谓对于将来的希望。希望是附丽于存在的,有存在,便有希望,有希望,便是光明。
题目描述
苏拉威西。距离地球进入木星洛希极限还有 $L$ 单位时间。蔡德仁收到了来自艾莉芬的“点燃木星计划”。计划要求他将附近所有救援队召集到同一台转向发动机处,清除障碍,并用“春节十二响”程序操纵发动机点燃木星。
转向发动机共有 $n$ 个,它们由 $n - 1$ 条道路相连。任意两个转向发动机都可以通过道路互相到达,二者的距离为其间最短路径的边数。
附近一共部署有 $k$ 支救援队 $s_1$, $s_2$, ..., $s_k$,每一支救援队有一个救援范围。救援范围是转向发动机集合的一个连通子集,其中任意两个发动机之间道路上的所有发动机都在救援范围中。
我们称一个发动机 $u$ 可被救援范围为 $S$ 的救援队到达,当且仅当 $u$ 在 $S$ 中,且 $S$中任意一个发动机 $v$ 到 $u$ 的距离都不大于 $L$。这样,无论救援队身在岗位的何处,他们都能在时间耗尽前抵达发动机 $u$。
蔡德仁要指挥 $k$ 支救援队集中到同一台发动机处。但由于通讯中断,蔡德仁不知 道每支救援队的救援范围。他想计算出可行的调度方案数,于是将问题输入电脑。
在这台电脑的另一面——你,需要帮他统计出,在多少种可能的部署方案中存在一 台能被所有救援队到达的发动机。一个方案指一组救援范围 $\left\{S_1, S_2, ..., S_k\right\}$;两个方案不同,当且仅当某个救援队 $s_i$ 在二者中的救援范围 $S_i$ 不同。在这次联合政府规划的饱和式救援中,两支队伍的救援范围可能相交甚至相同。
你知道,答案非常大。雪地车在成千上万个地标间穿梭,可能的救援范围浩如烟 海,集合所有队伍的方案却寥若晨星。但你没时间绝望,甚至没时间算出那个数字。
你只能算出答案对 $998244353$ 取模的结果。
那就是希望。
即便需要取模,也是光明。