ARC093D Dark Horse

题意：

有 个人，按照满二叉树的形态进行淘汰赛，一开始的排列顺序为所有 个排列之一。

你是第 个人，已知每一对人之间的实力关系，具体地说：

• 给出 个人 。
• 这 个人都打得过你。
• 你打得过除了这 个人之外的所有其他人。
• 对于剩下的情况（你不参与的情况），编号小的人胜利。

问你在所有的 种情况中，有多少种情况可以取得最终胜利。答案对 取模。

，时限 。

---

将比 强的 个人称为大佬。

首先将 放在第一个位置，最后将答案乘以 。

每个人都只会参与恰好 场对局，而你只需要保证这 场中没有遇到大佬。

各个对局分别对应大小为 的子树。

考虑容斥。钦定对局集合 ，则要在对应子树中安排选手，使得被钦定的子树的最小值是大佬。

记方案数为 ，则答案为 。

考虑状压 ，按照编号从大到小的顺序考虑大佬（因为编号越大限制越强）。

设 为考虑了前 个大佬，且子树集合 被覆盖的贡献和。

在安排第 个大佬时，可以不加入，也可以处理某个子树。

记 ，即已经被安排好的子树大小和。

转移： 其中 是选出未被占用的比 大的 个垫背者，最后将 加入有 种方法。

下降幂可以预处理阶乘后快速计算。

边界：。

最终需要考虑剩余数的排列，有

复杂度 。（所以其实 大一点也没关系）