自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:57:56，当前版本为作者最后更新于2018-02-15 12:44:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题没有剧情版题解qwq

可读题面：

求所有n个点带标号强连通竞赛图中哈密顿回路数量的平均值

解法0：

样例怎么全是1和-1啊

我if(i==2)puts("-1");else puts("1");吼不吼啊

期望得分0分，实际得分0分

解法1：

我会枚举！

枚举所有n个点的竞赛图，统计答案

时间复杂度$O(2^{C(n,2)}n!)$，期望得分12分，实际得分8~12分

解法2：

我会剪枝！

在解法1的基础上加一些玄学剪枝

时间复杂度$O($玄学$)$，期望得分24分，实际得分12~24分

解法3：

我会打表！

用解法1在自己电脑上多跑一会

时间复杂度同解法1，期望得分24分，实际得分12~16分

8的情况在我的电脑上要跑3天QWQ

解法4：

我会dp！

考虑所有n个点的竞赛图中哈密顿回路的总数，发现很好求，答案为$\frac{n!}{n}\cdot 2^{C(n,2)-n}$（一共有$\frac{n!}{n}$种哈密顿回路，每种哈密顿回路出现在$2^{C(n,2)-n}$种竞赛图里）

于是问题转化为了求强连通竞赛图的数量$f[n]$

随便推一推式子，发现$f[n]=2^{C(n,2)}-\sum_{i=1}^{n-1}{f[i]\cdot C(n,i)\cdot 2^{C(n-i,2)}}$（总竞赛图数减去不强联通的竞赛图数）

（统计不强连通的竞赛图数时可以枚举拓扑序最小的强连通分量，剩下的边随便连，就出现上面的式子啦$QwQ$）

时间复杂度$O(n^2)$，期望得分64分，实际得分52~64分

FAQ：为什么我只得了52分？

A：想到正解不预处理不还是$O(n^2log(n))$（facepalm）

解法5：

我会分治fft/多项式求逆！

优化一下上面的过程就好啦

时间复杂度$O(nlog^2(n))$或$O(nlog(n))$，期望得分100分，实际得分100分

FAQ：为什么我写了正解只得了76分

A：你很可能没开long long。。