#P7218. [2023省队模拟]最终对决
[2023省队模拟]最终对决
题目描述
MOSS 先构造一棵包含 个带编号顶点的树 ,每个顶点的度都不超过 。
接下来 Bob 选择两个不同的顶点 ()。记从 到 的最短路径上依次经过的顶点编号为 。
最后,MOSS 选择一个整数 ()和以下一种操作:
- 保留 ,将后缀倒序后每项加上 。所得序列为 $a_1,\ldots,a_i,a_k+a_i,a_{k-1}+a_i,\ldots,a_{i+1}+a_i$。
- 保留 ,将后缀的每一项 替换为 。所得序列为 $a_1,\ldots,a_i,a_i-a_{i+1},a_i-a_{i+2},\ldots,a_i-a_k$。
若操作后的序列严格单调(严格递增或严格递减),则 MOSS 获胜,否则 Bob 获胜。
双方都按最优策略行动。若存在多种必胜策略,可以任选其一。若必败,也可以任意决策。
求所有可能的最终局面 的个数,其中 分别表示选择第一种、第二种操作。答案对 取模。
输入格式
一行两个整数 。
输出格式
输出一行一个整数,表示答案。
样例输入 1
2 1
样例输出 1
4
样例输入 2
5 3
样例输出 2
1720
数据范围与约定
对于所有数据,,。大样例来自最终数据。
| 子任务 | 特殊限制 | 分值 | 依赖 |
|---|---|---|---|
| 1 | 5 | 无 | |
| 2 | 15 | ||
| 3 | |||
| 4 | 20 | 1 | |
| 5 | 15 | 1、4 | |
| 6 | 无特殊限制 | 30 | 1、2、3、4、5 |