题解 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。。