BZOJ-3456. 城市规划

题目要求求出有 n (n \leq 130000) 个点的有标号简单连通无向图的个数,答案 \bmod 1004535809 (479 \times 2^{21} + 1),是个质数

比如三个点的情况

graph-3node

题目链接:BZOJ-3456

首先可以设 f(n) 表示有 n 个点的有标号简单连通无向图的个数,g(n) 表示有 n 个点的有标号简单无向图的个数(也就是不要求连通)

g(n) 是很好求的,因为 n 个点,最多 n \choose 2 条边,因此

 g(n) = 2^{n \choose 2}

又因为一个有标号简单无向图是由很多连通分量组成的,为了避免重复计数,我们枚举点 1 所在的连通块大小(其余的点随便连边,因为 1 号点所在连通块已经确定,其它怎么连都不会重复)

 g(n) = \sum_{i = 1}^{n} {{n - 1} \choose {i - 1}} f(i) g(n - i)

我们把 g(n) 代入

 2^{n \choose 2} = \sum_{i = 1}^{n} {{n - 1} \choose {i - 1}} f(i) 2^{{n - i} \choose 2}

然后两边同时除以  (n - 1)!

 \frac{2^{n \choose 2}}{(n-1)!} = \sum_{i = 1}^{n} \frac{f(i)}{(i-1)!} \frac{2^{{n - i} \choose 2}}{(n-i)!}

现在你会发现这是个卷积的形式!定义函数 F(x), G(x), C(x)

 \begin{eqnarray*} F(x) &=& \sum_{n=1}^{\infty} \frac{f(n)}{(n-1)!}x^n \\ G(x) &=& \sum_{n=0}^{\infty} \frac{2^{n \choose 2}}{n!}x^n \\ C(x) &=& \sum_{n=0}^{\infty} \frac{2^{n \choose 2}}{(n-1)!}x^n \\ \end{eqnarray*}

可以得到

 C(x) = F(x)G(x)

将其放在 \bmod x^{n+1}

 \begin{eqnarray*} C(x) &\equiv& F(x)G(x) \pmod{ x^{n+1} } \\F(x) &\equiv& C(x)G^{-1}(x) \pmod{ x^{n+1} } \end{eqnarray*}

这样求出 G(x) 的逆元然后和 C(x) 乘起来就可以得到 F(x),也就是答案了,由于模数十分特殊,可以利用 FFT 优化(多项式求逆看这里

不知道为什么似乎跑得好快?Screenshot from 2015-05-28 12-41-58

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/bzoj-3456

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

3 thoughts on “BZOJ-3456. 城市规划

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.