BZOJ 3456: 城市规划(dp+多项式求逆)
解题思路
这道题就是求带标号的无向连通图个数,首先考虑\(O(n^2)\)的做法,设\(f_i\)表示有\(i\)个节点的无向连通图个数,那么考虑容斥,先把所有的无向图求出,即为\(2^{C(n,2)}\),再减去不联通的情况,而计算不联通情况时可以枚举\(1\)号点这个联通块的大小,就有方程
\[f_i=2^{C_i^2}-\sum\limits_{j=1}^{i-1}C_{i-1}^{j-1}2^{C^2_{i-j}}f_j\]
发现这样的时间复杂度为\(O(n^2)\)的,无法通过本题。考虑优化,我们设法把左右两边的\(f\)合并,可以给式子同时除一个\((i-1)!\),可得
\[\frac{f_i}{(i-1)!}=\frac{2^{C_i^2}}{(i-1)!}-\sum\limits_{j=1}^{i-1}\frac{2^{C^2_{i-j}}f_j}{(j-1)!(i-j)!}\]
发现右边假设\(j\)枚举到\(i\)正好是左边,那么就移项。
\[\sum\limits_{j=1}^i\frac{C^{2}_{i-j}f_j}{(j-1)!(i-j)!}=\frac{2^{C_i^2}}{(i-1)!}\]
右边是卷积的形式
\[\sum\limits_{j=1}^i\frac{f_j}{(j-1)!}*\frac{2^{C^2_{i-j}}}{(i-j)!}=\frac{2^{C^2_i}}{(i-1)!}\]
设\(A=\sum\limits_{i=1}^n\dfrac{f_i}{(i-1)!}x^i\),\(B=\sum\limits_{i=0}^{n-1}\dfrac{2^{C_i^2}}{i!}x^i\),\(C=\sum\limits_{i=1}^n\dfrac{2^{C_i^2}}{(i-1)!}x^i\),则
\[A*B=C\]
\[A=C*B^{-1}\]
多项式求逆即可,时间复杂度\(O(nlogn)\)
最新文章
- 有wsdl地址生成客户端调用
- 菜鸟-教你把Acegi应用到实际项目(9)-实现FilterInvocationDefinition
- UITabbar的简单操作和实际应用
- [转载]中国天气网API
- testng 注解
- PHP中 magic_quotes_gpc 和 magic_quotes_runtime 区别及其反斜线转义问题
- MVC分层含义与开发方式
- angularjs应用prerender.io 搜索引擎优化实践
- 关于Java的发展前景
- jquert 判断checkbox 是否选中
- php缩放gif和png图透明背景变成黑色的解决方法_php技巧
- html_jQuery_ajax
- mvc 路由伪静态实现
- 讲解wpe抓包,封包
- c# Redis 使用
- AOJ 2249 Road Construction (dijkstra)
- Vue基础以及指令
- File ";/usr/bin/yum";, line 30 except KeyboardInterrupt, e:
- 2018.11.01 NOIP训练 梭哈(模拟)
- Java设计模式学习记录-策略模式