AT_arc083_d [ARC083F] Collecting Balls 笔记

模拟赛 #46 T3。

分析一下，如果有一个机器人对应的一条直线都没有球捡，那就不可能捡完，输出 $0$，好像没有其他不合法的情况了。

一个球和 $(x,y)$ 有关，按照二分图的套路我们令 $x\to y+n$ 连无向边，若最终决定这条边指向 $x$，就说明由机器人 $(x,0)$ 领取，否则由 $(0,y)$ 领取。

由于每个机器人只捡一个球，因此可以发现建出来的图是基环树森林。

现在考虑决定边的指向，可以发现这是内向基环树森林，因为每个点的入度为 $1$。可以发现每棵基环树互相独立，因此我们考虑其中一棵基环树，找出他的环，按照正向 / 反向就有两种可能，于是我们遍历一次就能得到每个点领取了哪条边。但是我们能捡到这个球的条件是没有被阻挡，若 $(x,0)$ 领取 $(x,y)$，则所有满足 $y^{\prime }<y$ $(x,y^{\prime })$ 的小球都要先被领取；若 $(0,y)$ 领取 $(x,y)$ 同理。因此，对一个点进行领取操作的顺序构成了拓扑序。

现在要求拓扑序计数，据说这是没有多项式做法的，因此我们继续挖掘性质。

研究一下这个拓扑序，结合题意理解，每个 $x$ 机器人只会是一个 $y$ 机器人的前提，每个 $y$ 机器人只会是一个 $x$ 机器人的前提，因此每个节点只有一条出边，这是一棵内向树。

现在我们由一棵基环树 $i$ 得出了若干个内向拓扑树，现在要求拓扑序个数 $f_i$，设拓扑树上每个节点的子树大小是 ${\mathrm{sz}}_u$，内向拓扑森林总大小，也就是基环树的大小为 ${\mathrm{SZ}}_i$，则有

$$f_i=\frac{{\mathrm{SZ}}_i!}{\prod {\mathrm{sz}}_u}$$

考虑先给节点随便排序，对于一棵以 $u$ 为根的子树，根节点在拓扑序中必须出现在这 ${\mathrm{sz}}_u$ 个节点的第一个，因此除去了 ${\mathrm{sz}}_{\mathrm{u}}$ 的方案数。

接着再考虑把基环树森林的答案拼起来，可以发现各个基环树间操作顺序任意排列，因此就是多重集的排列数，最终的答案就是

$$\frac{n!}{\prod ({\mathrm{SZ}}_i!)}\times \prod f_i$$

时间复杂度 $O(n)$，空间复杂度 $O(n)$。