目录
luogu P4233 射命丸文的笔记
如果一个竞赛图含有哈密顿回路，则称这张竞赛图为值得记录的。
从所有含有 n 个顶点（顶点互不相同）的，值得记录的竞赛图中等概率随机选取一个。
求选取的竞赛图中哈密顿回路数量的期望值。
性质1：有哈密尔顿回路等价于强连通。
性质2：竞赛图缩点是一条链状DAG，一个点向后继所有点连边。
一个竞赛图的所有哈密尔顿回路有\(2^{C(n,2)-n}*\frac{n!}{n}\)(枚举回路的n条边再枚举竞赛图其他边)，所以这题只要求一下有都少个图满足条件，即有多少个强连通竞赛图。
也就是说有多少个竞赛图缩点后是一个点。
小小容斥一下。
\(f[i]=2^{C(i,2)}-\sum_{j=1}^{i-1}C(i,j)*f[j]*2^{C(i-j,2)}\)
AC还要优化到\(log^2n\)，分治ntt，这题不写。
CF1498E Two Houses
n=500的竞赛图，给所有的入度，问最大的强连通点对的|du[i]-du[j]|最大是多少。交互询问x能否到y，输出Yes时必须结束程序输出答案,输出No可以继续问，所有度数互不相同。
可以用竞赛图性质：如果 x 的出度大于 y 的出度，则 x 可以到达 y。然后n^2拿出所有可能从大到小询问即可。
或者用更强的性质：（竞赛图强连通分量判定定理）将入度从小到大排序。这样极大scc在区间上连续，且右端点满足判定定理\sum=C(n,2)。
直接不用询问就能做完了。