ARC083D Collecting Balls

题意 ： 在平面直角坐标系上有 个小球，第 个小球在 ，满足 。

有 个 A 类机器人，第 个在 ，有 个 B 类机器人，第 个在 。

启动一个 A 类机器人后，它会向右走，将碰到的第一个球收集起来，并消失。

启动一个 B 类机器人后，它会向上走，将碰到的第一个球收集起来，并消失。

只有上一个机器人返回起点后，下一个机器人才会被启动。

求有多少种启动机器人的顺序，能够收集完所有小球。方案数对取模 。

，时限 。

---

Part1

记第 个 A 类机器人为 ，第 个 B 类机器人为 。

对于球 ，它可以被机器人 或者 清除。

考虑建立图论模型，连边 。对于每条边，必须选择一个端点来将其收集。

不难发现，若某个连通块中 点数 边数，则无解。又因为本题中 总点数 总边数，故图一定是基环树森林。

我们将每条边定向，指向用于收集它的点。不难发现，唯一的方案是定成基环外向树，这样每个点的入度都为 。

Part2

在确定了机器人和球的匹配的基础上，考虑如何处理“机器人每次只会拿最近的球”的约束。

若 要收集球 ，则对于满足 的其他球 ，必须先收集。

（此时， 的其他球 必然由 B 类机器人收集）

对于 也有类似的约束。

若机器人 必须先于 行动，则连边 ，合法排列数即为该有向图的合法拓扑序数。

观察该有向图的性质 ：

• 每个点只会向右或向上连边，故该图为 。

• 对于某个 B 类机器人，只可能向至多一个 A 类机器人连边。A 类机器人类似。

  故每个点只有至多一个出边，图为内向树森林。

对内向树森林求拓扑序数目是经典问题。

记森林总点数为 ，节点 的子树大小为 ，则拓扑序数目为：

• 证明：考虑 DP。

  注意到，森林等价于将所有树连到一个新点上形成的树。

  对于节点 ，设儿子分别为 。记点 子树内的拓扑序数目为 。

  将 删除，看做森林。利用多重排列归并儿子的拓扑序，则：

  利用上式归纳，假设 的子树内都满足结论：

  于是证毕。

Part3

接下来考虑，对于多种机器人和球之间的匹配，如何求答案的和。

Part1 中发现，生成匹配的图为基环树森林，我们对每棵基环树分别处理，最后用多重排列归并。

对于某棵基环树，将其变为基环内向树的方案数总有两种，因为环有两种方向。

对这两种匹配分别用 Part2 中的算法求解合法排列数即可。

复杂度为 。