- 给定一张(n)个点(m)条边的图，设其中有(k)个连通块。
- 要求加入(k-1)条边使得图连通，求方案数。
- (n,mle10^5)
(prufer)序列+生成函数
设第(i)个连通块的点数为(a_i)，度数为(d_i+1)。
(prufer)序列的知识告诉我们，这种情况下的生成树个数应该是(frac{(k-2)!}{prod_{i=1}^kd_i!})。
由此得出答案的计算式：
[sum_{sum_{i=1}^kd_i=k-2}frac{(k-2)!}{prod_{i=1}^kd_i!}prod_{i=1}^ka_i^{d_i+1}=(k-2)!prod_{i=1}^ka_isum_{sum_{i=1}^kd_i=k-2}prod_{i=1}^kfrac{a_i^{d_i}}{d_i!}
]
前面的((k-2)!prod_{i=1}^ka_i)是一个常数项可以暂且不管，对于后面的东西先设出一个生成函数：
[F(x)=sum_{i=0}^{+infty}frac{x^i}{i!}=e^x
]
因此(prod)中的式子相当于是若干(F(a_ix))卷在一起，也就是(e^{a_ix})相卷，得到：
[[x^{k-2}]prod_{i=1}^ke^{a_ix}=[x^{k-2}]e^{sum_{i=1}^ka_ix}=[x^{k-2}]e^{nx}=frac{n^{k-2}}{(k-2)!}
]
这时候发现一个极好的事情，推得式子是一个常数项，且这里分母中的((k-2)!)恰好能和前面常数项中的((k-2)!)约掉！
于是最终的答案实际上是一个非常简单的式子：
[n^{k-2} imesprod_{i=1}^ka_i
]
所以具体实现你只需要写一个并查集。。。
代码：(O(nalpha(n)))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
using namespace std;
int n,m,X,g[N+5],f[N+5];I int fa(CI x) {return f[x]?f[x]=fa(f[x]):x;}
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int main()
{
RI i,x,y;for(read(n,m,X),i=1;i<=m;++i) read(x,y),(x=fa(x))^(y=fa(y))&&(f[y]=x);//并查集合并
RI t=1,k=0;for(i=1;i<=n;++i) ++g[fa(i)];for(i=1;i<=n;++i) fa(i)==i&&(t=1LL*t*g[i]%X,++k);//统计连通块大小之积及连通块个数
if(k==1) return printf("%d
",1%X),0;//如果k=1，答案尽管仍能用上式计算为n^(-1)*n=1，但n^(-1)无法得出，需特判
for(i=1;i<=k-2;++i) t=1LL*t*n%X;return printf("%d
",t),0;//乘上n^(k-2)
}