Luogu4233 射命丸文的笔记

题意：

定义竞赛图为：有向图，每两个点之间都有一条边，方向任意。

求所有有哈密顿回路的带标号竞赛图中，哈密顿回路条数的期望。

答案对 取模，，时限 。

---

首先考虑可能的哈密顿回路总数。哈密顿回路可以视作环排列，所以本质不同的回路共有 种。

每种回路的地位都是相同的，我们数一下每条回路会在多少种竞赛图中出现。显然，这条回路规定了恰好 条边的方向，其余的边都随意，方案数是 。

所以，回路的总条数是 -----

现在，只需要求出“有哈密顿回路的带标号竞赛图”个数作为分母就可以了。

充要条件是：图强连通。如果图是非强连通的，缩点后可以当做 DAG，那么一旦走到岔路里去就无法回头，肯定是无法形成回路的。反之，根据强连通图的定义就能够构造出一个大环来。

现在问题变成了“强连通竞赛图”计数。

考虑使用强连通竞赛图表示普通竞赛图，然后倒推。

设 是强连通竞赛图的 EGF， 则是普通竞赛图。考虑每条边的方向，易得 。

考虑将普通竞赛图缩成 DAG，这个 DAG 仍然是竞赛图。可以发现，由于每两个点之间都有连边，DAG 的拓扑序是唯一的。我们在此建立了双射，把 DAG 转化成了一排强连通竞赛图。

于是 。

即 ，解得 ，多项式求逆即可。复杂度 。