模拟赛 #46 T3。
分析一下，如果有一个机器人对应的一条直线都没有球捡，那就不可能捡完，输出 \(0\)，好像没有其他不合法的情况了。
一个球和 \((x,y)\) 有关，按照二分图的套路我们令 \(x\to y+n\) 连无向边，若最终决定这条边指向 \(x\)，就说明由机器人 \((x,0)\) 领取，否则由 \((0,y)\) 领取。
由于每个机器人只捡一个球，因此可以发现建出来的图是基环树森林。
现在考虑决定边的指向，可以发现这是内向基环树森林，因为每个点的入度为 \(1\)。可以发现每棵基环树互相独立，因此我们考虑其中一棵基环树，找出他的环，按照正向 / 反向就有两种可能，于是我们遍历一次就能得到每个点领取了哪条边。但是我们能捡到这个球的条件是没有被阻挡，若 \((x,0)\) 领取 \((x,y)\)，则所有满足 \(y'< y\) \((x,y')\) 的小球都要先被领取；若 \((0,y)\) 领取 \((x,y)\) 同理。因此，对一个点进行领取操作的顺序构成了拓扑序。
现在要求拓扑序计数，据说这是没有多项式做法的，因此我们继续挖掘性质。
研究一下这个拓扑序，结合题意理解，每个 \(x\) 机器人只会是一个 \(y\) 机器人的前提，每个 \(y\) 机器人只会是一个 \(x\) 机器人的前提，因此每个节点只有一条出边，这是一棵内向树。
现在我们由一棵基环树 \(i\) 得出了若干个内向拓扑树，现在要求拓扑序个数 \(f_i\)，设拓扑树上每个节点的子树大小是 \(\mathrm{sz}_u\)，内向拓扑森林总大小，也就是基环树的大小为 \(\mathrm{SZ}_i\)，则有
考虑先给节点随便排序，对于一棵以 \(u\) 为根的子树，根节点在拓扑序中必须出现在这 \(\mathrm{sz}_u\) 个节点的第一个，因此除去了 \(\mathrm{sz_u}\) 的方案数。
接着再考虑把基环树森林的答案拼起来，可以发现各个基环树间操作顺序任意排列，因此就是多重集的排列数，最终的答案就是
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。