萌新初学拉格朗日反演，这个看起来很对所以应该是对的吧？
把 \(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}\)．
标签：标号,拉格朗,个点,Cayley,连成,反演,cdots From： https://www.cnblogs.com/do-while-true/p/16811585.html