题解 P4233 【射命丸文的笔记】

· · 题解

本题没有剧情版题解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。。