[关闭]
@l1ll5 2020-08-11T02:51:44.000000Z 字数 1135 阅读 612

0811,E


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


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

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


引理2:竞赛图中,对于一个 个点的强连通分量,大小为 的简单环均存在。

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

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

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

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

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

注意 只能同时为空(否则和强连通矛盾),算法可行。


此时问题转化为:有多少个大小为 的竞赛图,至少存在一个大小至少为 的强连通分量。

考虑补集转化,求出 表示只包含大小严格小于 的强连通分量的竞赛图个数。


表示 个点的强连通竞赛图个数。
表示 个点的竞赛图个数。

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

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

对于 的求解过程,仍然是补集转化。

考虑它们的生成函数

多项式求逆即可解决。

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注