0811，E

---

题意：有多少 $n$ 个点的竞赛图至少有一个大小恰好为 $k$ 的简单环

---

引理1：对于一个给定的拓扑序，有且仅有一种对应的无环竞赛图。

证明：考虑拓扑排序的过程，导致产生多种情况的原因在于某一时刻存在多个 $deg=0$ 的点，由于竞赛图任意两点间均有边，则不可能存在这种情况。

---

引理2：竞赛图中，对于一个 $n(n \geq 3)$ 个点的强连通分量，大小为 $[3,n]$ 的简单环均存在。

证明：
一个常见的办法是考虑归纳，这里我们考虑一个构造性的方法。

由于原图强连通，易证存在大小为 $3$ 的环，现在考虑扩展它。

将其余节点划分为 $A，B，C$ 三个集合。
集合 $A$ 保存所有和环中的点的边都是入边的点。
集合 $B$ 保存所有和环中的点的边都是出边的点。
集合 $C$ 保存和环中的点的边既有入边也有出边的点。

如果 $C$ 非空
任取集合 $C$ 中一个点 $X$，显然可以在环中取相邻的两个点 $Y,Z$，使得有边 $X->Y,Z->X$，此时 $X$ 可以加入环中。

如果 $C$ 为空
在A中取点 $X$，$B$中取点$Y$，使得存在一条 $X->Y$ 的边。由于强连通，这样的点对必然存在。那么可以用这两个点替代环上的任意节点，此时环的大小增加 $1$。

注意 $A$和 $B$ 只能同时为空（否则和强连通矛盾），算法可行。

---

此时问题转化为：有多少个大小为 $n$ 的竞赛图，至少存在一个大小至少为 $k$ 的强连通分量。

考虑补集转化，求出 $h(n)$ 表示只包含大小严格小于 $k$ 的强连通分量的竞赛图个数。

令
$f(n)$ 表示 $n$ 个点的强连通竞赛图个数。
$g(n)$ 表示 $n$ 个点的竞赛图个数。

$$g(n)= 2^{\binom{n}{2}}$$

由引理1，只需考虑拓扑序最小的连通分量的情况。

$$h(n)=\sum_{i=1}^{k-1} h(n-i) \cdot f(i) \cdot \binom{n}{i}$$

$$\frac{h(n)}{n!} = \sum_{i=1}^{k-1} \frac{h(n-i)}{(n-i)!} \cdot \frac{f(i)}{i!}$$

注意到只要处理出 $f$,是一个常系数线性递推的形式。

对于 $f$ 的求解过程，仍然是补集转化。

$$f(n)=g(n)-\sum_{i=1}^{n-1} g(n-i) \cdot f(i) \cdot \binom{n}{i}$$

$$\frac{f(n)}{n!}=\frac{2g(n)}{n!}-\sum_{i=0}^{n-1} \frac{g(n-i)}{(n-i)!} \cdot \frac{f(i)}{i!}$$

考虑它们的生成函数

$$F=\sum_{i=0}^{\infty}\frac{f(i)}{i!} x^i,G=\sum_{i=1}^{\infty}\frac{g(i)}{i!} x^i$$

$$F=2G-F\times G +1$$

$$F=2-\frac{1}{G+1}$$

多项式求逆即可解决。

结合上文的常系数线性递推，复杂度为 $O(klog_klog_n)$。可能需要一定的常数优化以避免TLE。