有一个大小为\(n\)的完全图，其中形如\((i,i+1)\)的边叫“特殊边”。
对于一个生成树，设\(x\)为生成树中“特殊边”的个数，则它的价值为\(2^xx\)
问所有生成树的价值和。
\(n\leq 5e5\)
不存在思路。
直接流氓做法：矩阵树+拉格朗日差值，简单粗暴地\(O(n^4)\)拿了\(23\)分。
假如保留了至少若干条特殊边，形成了\(m\)个连通块，那生成树的个数就是\(n^m\prod s_i\)。
\(s_i\)表示第\(i\)个连通块的大小。
为什么是至少呢？因为我没有办法保证生成树的时候还选了特殊边啊……
注意一下，这个“至少”选若干条边，不是粗暴地将所有大于等于至少的边数的方案相加，而是枚举至少选的边其它任意选。两者有着本质的区别。
怎么证明……
一开始看着感觉挺对了，回家后感觉不对劲，于是真正地学了一下purfer序，发现它还是对的。
purfer序的构造：对于所有度数为\(1\)的点，找到其中最小的，删去并将其连接的节点加入purfer序列末端。一直操作至只有两个点为止。
还原：先计算出所有点的度数（在purfer序中的出现次数加一）。找到不在当前\(purfer\)序列且度数为\(1\)的最小点，和队头连边，将两者度数各减一，删去队头。循环操作。
可以感受到purfer序列具有唯一性。
再看这题，如果将一个连通块看成一个整体，一样地构造这个purfer序。度数为\(1\)的某个连通块删去时，它连接的点记为连向的具体的点（而不是连通块）。于是就有了\(n^{m-2}\)。
但是，这样没有计算这个连通块具体是哪个点向父亲连出这条边（“父亲”定义为删去一个点时与它相连的点，特别地，定义最后留下的两个点互为对方的父亲）。
于是最终方案数就是\(n^{m-2}\prod s_i\)。
先给一个比较朴素的思路：
设至少删去了\(k\)条边，\(m=n-k\)（即连通块的个数）
求它的方案数。方案数为\(n^{m-2}\sum_{每一种方案} ( \prod s_i )\)
考虑算后面这个东西。
这相当于是数轴上\(n\)个数划分成\(m\)段，贡献为每段的长度乘积，求所有方案的贡献和。
生成函数一下：
记至少删去\(k\)条边的方案数为\(f(k)=n^{m-2}C_{n+m-1}^{n-m}\)，恰好删去\(k\)条边的方案数为\(g(k)\)
二项式反演得
这个二项式反演可以用NTT优化到\(O(n\lg n)\)
注意到以上方法并没有用到题目中价值为\(2^xx\)的性质
从组合意义上考虑。假如价值是\(2^x\)，会有怎样的意义呢？
考虑对于某种方案，它选了至少\(k\)条边。
\(f(k)\)中会算\(C_{k}^{k}\)次，\(f(k-1)\)中会算\(C_{k}^{k-1}\)次，\(f(k-2)\)中会算\(C_{k}^{k-2}\)次……
加起来，会发现它被算了\(2^k\)次，恰好就是它的价值。
于是答案就是\(\sum f(k)\)
那么价值为\(2^xx\)呢？
可以视为在\(x\)条边中选任意条边，并且在\(x\)条边中选任何一条边，两者取交集。（注意着两个“选”中没有任何关联）
对于一个恰好选\(k\)条特殊边的方案，考虑有什么方法可以恰好计算它\(2^kk\)次。
注意到组合数有这样的性质：\(\sum_{i=1}^{k}iC_k^i=2^{k-1}k\)
于是可以这样，将\(f(i)\)改成\(f‘(i)\)，表示：至少选了\(i\)条边，并且在这\(i\)条边中对其中的某一条边标号。
显然\(f‘(i)=f(i)*i\)
于是答案就是\(2\sum f‘(k)\)
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mo 998244353
#define ll long long
#define N 500010
ll qpow(ll x,int y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n;
ll pw[N],fac[N*2],ifac[N*2];
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
int main(){
freopen("traffic.in","r",stdin);
freopen("traffic.out","w",stdout);
scanf("%d",&n);
fac[0]=1;
for (int i=1;i<=2*n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[2*n]=qpow(fac[2*n]);
for (int i=2*n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
pw[0]=1;
for (int i=1;i<=n;++i)
pw[i]=pw[i-1]*n%mo;
ll ans=0;
for (int k=1;k<n-1;++k)
ans=(ans+k*pw[n-k-2]%mo*C(2*n-k-1,k))%mo;
ans=(ans+(n-1)*1)%mo;
ans=ans*2%mo;
printf("%lld\n",ans);
return 0;
}
生成函数和组合数是不得不绕过的坎……
原文：https://www.cnblogs.com/jz-597/p/13027755.html