首页 > 其他 > 详细

bzoj 3456 城市规划

时间:2019-01-15 16:45:55      阅读:144      评论:0      收藏:0      [点我收藏+]

求 n 个点简单无向连通图个数,膜 $1004535809$ (是一个质数,原根是 $3$)

$n \leq 130000$

sol:

推式子的方法...应该到处都有

记录一下指数生成函数 (EGF) 的做法

先设 $g(x)$ 为 n 个点简单无向图的 EGF ,可以知道 $g(x)=\sum\limits_{i=0}^{\infty} 2^{\binom{i}{2}} \times \frac{x^i}{i!}$

然后考虑求 n 个点简单无向连通图的 EGF ,记为 $f(x)$

一个不一定连通的图由若干个连通块组成,枚举一下连通块的大小得到 $g(x)=\sum\limits_{i=0}^{\infty} \frac{(f(x))^i}{i!}$

可以理解成,包含 1 个连通块的是 $f(x)$ ,两个连通块的是 $\frac{1}{2} \times (f(x))^2$ ,三个连通块的是 $\frac{1}{6} \times (f(x))^3$ ...

然后考虑 $e^x$ 的泰勒展开,$e^x = \sum\limits_{i=0}^{\infty} \frac{x^i}{i!}$ ,可以知道 $g(x) = exp(f(x))$ ,则 $f(x) = ln(g(x))$ 

多项式求 ln 即可,答案就是 $[x^n]f(x) \times n!$

bzoj 3456 城市规划

原文:https://www.cnblogs.com/Kong-Ruo/p/10272399.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!