3456专题

BZOJ 3456 城市规划 (组合计数、DP、FFT)

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=3456 著名的多项式练习题,做法也很多,终于切掉了纪念 首先求一波递推式: 令\(F(n)\)为\(n\)个点的有标号无向连通图的个数,则考虑补集转化为有标号无向不连通图的个数,然后枚举\(1\)号点所在联通块的大小: \[F(n)=2^{n\choose 2}-\sum^{n-1}_