萌新初学拉格朗日反演,这个看起来很对所以应该是对的吧?


\(n\) 个点连成有 \(k\) 棵树的森林,并且要求 \(1,2,\cdots,k\)\(k\) 个点两两不在同一棵树的方案数。

首先通过看错题求个连成 \(k\) 棵有根树的个数。

\(T\) 有标号有根树的 EGF,则 \(T=ze^T\),答案即为 \(n![x^n]T^k\)

拉格朗日反演。

\(T\) 的复合逆 \(G=\frac{z}{e^z}\),再令 \(H(x)=x^k\)

\[\begin{aligned} n![x^n]T^k&=n![z^n]H(T)\\ &=(n-1)![z^{n-1}]H'(z)\left(\frac{z}{G}\right)^n \\ &=k(n-1)![z^{n-1}]z^{k-1}e^{nz} \\ &=k(n-1)![z^{n-k}]e^{nz} \\ &=k(n-1)!n^{n-k}\frac{1}{(n-k)!} \\ &=k\cdot n^{n-k-1}\cdot n^{\underline k} \end{aligned} \]

然后考虑原问题是 \(1,2,\cdots,k\) 两两不在同一棵树,那么这些点就可以看作它所在的树的根,然后考虑对这样一个方案给它重标号使得根并非是强制 \(1,2,\cdots ,k\).首先 \(>k\) 的标号在分配标号后相对顺序不能改变,但是 \(1,2,\cdots,k\) 这些标号的相对顺序可以改版,所以需要乘一个 \(n^{\underline k}\) 来得到 \(k\) 棵有标号有根树个数。

反过来,连成 \(k\) 棵有标号有根数的方案数除掉 \(n^{\underline k}\) 即为原问题所求。

所以把 \(n\) 个点连成有 \(k\) 棵树的森林,并且要求 \(1,2,\cdots,k\)\(k\) 个点两两不在同一棵树的方案数是 \(k\cdot n^{n-k-1}\)

原文地址:http://www.cnblogs.com/do-while-true/p/16811585.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性