题解 P4233 【射命丸文的笔记】
oscar
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。。