whk 考试前写题解攒 rp 有用吗
仍然是讲讲想出来的过程。
首先，我们只需要关心一个联通块中有哪些点，而不用关心图的具体形态。
然后，将每个连通块看作一个点，就变成了一个无根树计数问题，但是带权值。首先想到 prufer 序列。
prufer 序列的定义：一棵无根树中，每次将编号最小的叶子取出来，将和它相连的点编号加入序列，然后删掉这个叶子。重复操作知道剩下的点只有两个，其中有一个一定是 \(n\)。形成的序列就是 prufer 序列。
然后发现我们可以参考无根树计数的方法来尝试计数。
无根树计数方法：发现 prufer 序列中每个位置都可以取到 \([1,n]\) 内的所有数，所以方案数即为 \(n^{n-2}\)。
发现带权之后，设第 \(i\) 个联通块大小为 \(c_i\)，则确定一个 prufer 序列 \(P\) 后，连边方案数分成两部分。下文 \(k\) 定义按照翻译。
-
第一部分，对于每个连通块，选择它记录 prufer 序列时，被删去时，和它相连的连通块中的一个点。这部分的方案数为 \(\prod_{i\le k-2}c_{P_i}\times c_k\)。后面要乘上 \(c_k\) 的原因是最后剩的两个点还要计算一次。
-
第二部分，对于每个连通块，选择它记录 prufer 序列时，被删去时，它连向相连连通块的那条边，所连的这个连通块的一个点。这部分的方案数是 \(\prod_{i\le k-1}c_i\)，原因显然。
所以乘起来即为 \(\prod_{i\le k-2}c_{P_i}\times \prod_{i\le k}c_i\)。
但是我们还不知道 prufer 序列长什么样，但是发现这是经典的问题：在若干个集合中各选一个元素相乘，所有乘积之和。这个和就是所有集合内元素之和之积。
回到原题中，每个集合的和都是 \(n\)，所以最后答案即为 \(n^{k-2}\times\prod_{i\le k}c_i\)。
别忘了 \(k=1\)。
同时别忘了 \(mod=1\)。
code：
点击查看代码
int n,m,mod,c[N];
struct DSU{
int fa[N];
void init(){rep(i,1,n)fa[i]=i;}
il void merge(int x,int y){fa[find(x)]=find(y);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
}T;
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void Yorushika(){
scanf("%d%d%d",&n,&m,&mod);
T.init();
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
T.merge(u,v);
}
rep(i,1,n)c[T.find(i)]++;
int ans=1,cnt=0;
rep(i,1,n)if(c[i])ans=1ll*ans*c[i]%mod,cnt++;
if(cnt==1)puts(mod==1?"0":"1");
else printf("%lld\n",1ll*ans*qpow(n,cnt-2)%mod);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}