题解 P5807 【Which Dreamed It/【模板】BEST 定理】

· · 题解

前置知识

Best 定理

对于一个有向欧拉图，记点 i 的出度为 \text{out}_i，其本质不同的欧拉回路个数为：

T\prod_{i}(out_i-1)! 显然，$T$ 可以有矩阵树定理求得。 宣传下：[矩阵树定理学习笔记](https://www.cnblogs.com/juju527/p/15183866.html)。 ##### 证明 记 $s$ 为起点。 对于一条欧拉回路，我们把所有点的最后一条出边拿出来去除掉 $s$ 的出边， 一定形成一棵以 $s$ 为根的内向树。 原因是如果成环，由于所有点出度等于入度，环上最后走的一条边到达的位置仍会有一条出边未走，矛盾。 此时其他所有非树边随便排列，考虑构造一组方案。 至于从根出发的非树边有 $out_s$ 条，全部重排应该是 $out_s!$。 但考虑从任意一条边开始，由于最终走了一条回路，所以会造成一次轮换。 最后一条本质相同的的回路将被算 $out_s$ 次，最终除掉即可。 从 $s$ 出发按选择的出边顺序走，最后走树边由于出度等于入度，一定能走完所有边。 由于所有点的最后一条出边中一定有欧拉回路顺序中的最后一条边，该条边一定回到 $s$，得到回路。 ### $\texttt{Solution}

模板题，题目中要求的答案即为有向图欧拉回路计数。

值得注意的是，其为并未去除循环同构的欧拉回路。

我们得到答案后应乘上 out_1，原因在上述证明中。

边界情况是注意 Best 定理是在欧拉图上使用的，

应特判不是欧拉图的情况。

时间复杂度 O(Tn^3)。

code