Ember 和 Storm 正在玩游戏。首先,Ember 构造一棵 个节点且每个节点度数不超过 的带节点编号的树 。然后,Storm 选择两个不同的节点 和 ,并写下从 到 路径上的节点编号,记为序列 。最后,Ember 在序列中选择一个位置 ,并在以下两个操作选择一个执行:
- 翻转 并将这一段加上 ,操作后序列变为 ,,,,
- 取负 并将这一段加上 ,操作后序列变为 ,,,,
如果最后的序列是严格单调的,则 Ember 获胜,否则 Storm 获胜。
游戏情形可以用一个元组 来描述, 为翻转或是取负取决于 Ember 的决策。若 Ember 和 Storm 都使用最优策略(若有多种必胜策略,任选一种执行;若必败,也任选一种执行),试统计所有可能的游戏情形的数量,并输出其取模 的结果。
Constraints
, ,
Solution
首先,Ember 一定会构造出一棵能让自己必胜的树。而 Ember 获胜当而仅当原序列 为单调的或是单峰的;且对于每一个合法的序列,有 种合法的 的组合。没有什么好证明的……在草稿纸上自己模拟一下两种操作就可以得到了。
问题转换为:统计满足以下条件的树的数量 :1. 包含个节点,2. 每个节点度数不超过 ,3. 树上任意两个节点间路径的编号序列为单调的或单峰的。最终答案为 。
而对于一棵合法的树,一定存在一个特殊点,满足以这个节点为起点或终点的所有路径都是单调的。为了方便统计,我们令合法树的根节点为特殊点。观察可得,对于一棵合法树,除根节点以外的子树都满足:父亲节点编号大于儿子编号,或是父亲编号小于儿子编号。所以我们只需要统计这两种情况的答案,然后在根节点处拼起来即可。而实际上,这两种情况是等价的。
令 表示节点数为 ,根节点度数为 ,且父亲编号小于儿子编号的方案数。
枚举当前要拼接的子树大小 ,钦定根节点编号最小,拼接过来的子树的根节点编号次小,可得到以下递推公式:
令 ,可得:
时间复杂度为 ,初始化 。
(这种方法是在评论区看到的……然后参考了一下wxh大爷的博客。官方题解给了另一种统计 数组的方式,要稍微复杂一些,以及因为不保证 是质数,会有一些细节需要处理。详见官方题解,细节处理详见评论区。)
统计出 数组后就可以开始拼接了,枚举满足父亲节点编号小于儿子编号的点数 、度数 , 满足父亲节点编号大于儿子编号的度数 ,可得到以下公式:
而实际上一棵合法树是可以有多个合法根的,比如最简单的 的情况,合法根既可以是 也可以是 。我们可以得出另一个结论,如果一棵树有多个合法根,那么这些点一定构成一条单调链,一端是 且 ,另一端是 且 ,中间是 且 ,我们把这棵树放在第一种情况统计。
得到最终公式:
Code
1 |
|