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

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