#P18897. [2026多校联测]重剪巡游录像
[2026多校联测]重剪巡游录像
题目描述
一场巡游表演结束后,摄影机器人留下了依次经过的路口编号,用来记录巡游路线。录像编辑员希望通过倒放某些片段调整这份记录;只有从同一个路口出发并回到该路口的片段才允许倒放。
巡游区域有 个路口,编号为 ,路口之间有 条双向道路,任意两个路口之间都存在道路相通,因此道路构成一棵树。
给出一份经过 次道路通行的巡游记录
记录中每两个相邻的路口之间必定有一条道路直接相连。允许反复经过同一个路口、同一条道路,保证这份记录至少访问每个路口一次。
编辑员可以进行有限次以下操作,也可以不操作:在当前记录中选择 ,且满足 ,将从位置 到位置 的整段记录逆序,其他位置不变。下一次操作仍以操作后的记录为准。
请统计:能通过这些操作得到多少份不同的记录,其字典序严格小于输入的原始记录?答案对 取模。
所有记录的长度均为 。比较字典序时,找到第一个不同的位置,该位置路口编号更小的记录字典序更小。通过不同操作过程得到的同一份记录只计一次;原始记录不计入答案。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示一条双向道路。
最后一行 个整数 ,表示原始巡游记录。
输出格式
输出一行一个整数,表示符合要求的不同记录数量对 取模的结果。
样例 1 输入
4 6
1 2
1 3
3 4
1 3 4 3 1 2 1
样例 1 输出
1
样例 1 解释
将原始记录整体逆序,得到 。原始记录的首尾均为 ,所以这是一次合法操作。
每条道路都恰好通行两次,路口 的访问必须包含在往返路口 的片段内部。因此只有上述两份不同记录,字典序更小的恰有一份。
样例 2 输入
3 7
2 1
2 3
2 3 2 1 2 1 2 3
样例 2 输出
2
样例 2 解释
每次从路口 离开,下一站只能为 或 。前 次离开后都会返回路口 ,最后一次必须走向终点 。前三次的下一站依次可以是 、 或 ;相同目的地不可区分。原记录对应第三种,因此有 份记录比它小。
子任务
对于所有测试数据,保证:,;道路构成树;记录中的编号都在 至 之间,相邻路口有道路直接相连,且记录访问所有路口。由此 。当 时,必有 。
各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | |
| 2 | 树为以路口 为中心的星形,且 | |
| 3 | 原始记录经过每条道路的次数均不超过 (两个方向合计) | |
| 4 | 40 | 无额外约束 |