Gym102028G Shortest Paths on Random Forests 生成函数、多项式Exp
神仙题……
考虑计算三个部分：1、\(n\)个点的森林的数量，这个是期望的分母；2、\(n\)个点的所有森林中存在最短路的点对的最短路径长度之和；3、\(n\)个点的所有路径中存在最短路的点对的个数之和，这个是用来计算需要取到\(m\)的点对的数量。
对于1，这个就直接对着树的数量的EGF做多项式exp即可。因为点之间有序所以用EGF，\(n\)个点的树的数量由Cayley定理就是\(n^{n-2}\)。
对于3，考虑枚举一个连通块大小，那么这种连通块大小的所有树的存在最短路的点对之和就是\(n^{n-2} \binom{n}{2}\)。然后我们需要求这个连通块在哪些森林中出现过，我们就需要拼一个森林进去，所以直接拿这个的EGF跟1中求出来的多项式做一个卷积就可以了。
对于2，发现那个平方不是很好搞，于是可以考虑平方的组合意义，实际上就是在\(i,j\)路径上的边上有序地任取两条边。我们可以考虑先枚举两条边，然后再考虑这两条边会在哪些路径上做出贡献。注意到两条不重合的边会把树分为三个连通块，而两条重合的边会分为两个连通块，那么我们可以再次交换求和顺序，先枚举两个/三个连通块，然后考虑如何在这两个/三个连通块之间连边、选择\(i,j\)。
考虑三个连通块的情况，两个连通块的情况类似。注意到如果三个连通块大小为\(a_1,a_2,a_3\)，边固定为1连向2、2连向3，\(i\)在1、\(j\)在3，那么连边的方式就有\(a_1a_2 \times a_2a_3\)种，选择起点的方式有\(a_1\)种，选择终点的方式有\(a_3\)种，那么总贡献就是\(a_1^2a_2^2a_3^2\)，只和连通块大小有关。不难再构造一个生成函数，每个位置表示大小为\(x\)的连通块的贡献，那么这个生成函数的平方和三次方就是选择两个连通块和三个连通块的方案。
那么我们就只要考虑这个连通块会出现在哪些森林里，和3过程一样卷上1求出来的多项式就可以了。
值得注意的一点是，求2的过程中，因为有序枚举这两条边是存在两种方案的，所以选择三个连通块的所有方案需要乘上2；在求2的过程中，点对\(i,j\)和点对\(j,i\)都会被计算，所以2的所有答案还要除以2。
最新文章
- Xcode8中处理打印日志的配置
- VI,CI,UI
- No mapping found for HTTP request with URI
- [转]ubuntu server上网配置
- 物理CPU、物理核跟逻辑核的区分
- 用C++ 设计一个不能被继承的类
- 黑马程序员_JavaIO流（二）
- XMPP 服务器 Openfire 的 Emoji 支持问题（进行部分修改）
- Linux在shell中进入python敲方向键出现「^[[C^[[D」的解决办法
- PHP写的验证码类
- FreeRTOS 任务与调度器（1）
- Python 注释，类，属性，方法，继承
- LVS NAT/DR
- 程序员训练机器学习 SVM算法分享
- wcf中的Message类
- 面向服务的SOA架构与服务总线ESB
- 【Android】17.5 利用Messenger实现进程间通信（IPC）
- rabbitMQ应用，laravel生产广播消息，springboot消费消息
- express路由和中间件
- SVN使用—高级用法