差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:prufer序列 [2020/08/16 11:39]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:prufer序列 [2020/08/16 15:17] (当前版本)
jxm2001
@@ 行 26: / 行 26: @@
 ===== Prufer 的编码与解码 =====
+[[https://www.luogu.com.cn/problem/P6086|洛谷p6086]]
 考虑如何根据树建立 $\text{Prufer}$ 序列，同时如何根据 $\text{Prufer}$ 序列还原树。
@@ 行 76: / 行 78: @@
 ==== 习题一 ====
+[[https://www.luogu.com.cn/problem/CF156D|CF156D]]
+=== 题意 ===
+给定一个 $n$ 个点 $m$ 条边的带标号无向图，求添加最少的边使图连通的方案数。
+=== 题解 ===
+假设图中有 $k$ 个连通块，每个连通块中的点的个数为 $s_i$。先进行将每个连通块缩点，于是最终方案肯定为一个生成树。
+然后设每个点度数为 $d_i$，根据 $\text{Prufer}$ 序列性质，满足条件的生成树有 $\cfrac{(k-2)!}{\prod_{i=1}^k(d_i-1)!}$ 棵。
+而每棵生成树对应的方案数为 $\prod_{i=1}^k s_i^{d_i}$。设 $c_i=d_i-1$，答案为
+$$\sum_{\sum d_i=2k-2}\cfrac{(k-2)!\prod_{i=1}^k s_i^{d_i}}{\prod_{i=1}^k(d_i-1)!}=\prod_{i=1}^k s_i\sum_{\sum c_i=k-2}\cfrac{(k-2)!\prod_{i=1}^k s_i^{c_i}}{\prod_{i=1}^kc_i!}=\left(\sum_{i=1}^k s_i\right)^{k-2}\prod_{i=1}^k s_i=n^{k-2}\prod_{i=1}^k s_i$$
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+int p[MAXN],sz[MAXN],mod;
+int quick_pow(int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%mod;
+		a=1LL*a*a%mod;
+		b>>=1;
+	}
+	return ans;
+}
+int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+int link(int a,int b){
+	int x=Find(a),y=Find(b);
+	if(x!=y){
+		if(sz[x]>sz[y])swap(x,y);
+		p[x]=y,sz[y]+=sz[x];
+	}
+}
+int main()
+{
+	int n=read_int(),m=read_int(),k=0,ans=1,u,v;
+	mod=read_int();
+	_rep(i,1,n)p[i]=i,sz[i]=1;
+	while(m--){
+		u=read_int(),v=read_int();
+		link(u,v);
+	}
+	_rep(i,1,n){
+		if(i==Find(i)){
+			k++;
+			ans=1LL*ans*sz[i]%mod;
+		}
+	}
+	enter(k==1?1%mod:1LL*ans*quick_pow(n,k-2)%mod);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://ac.nowcoder.com/acm/contest/5672/I|牛客暑期多校(第七场) I 题]]
+=== 题意 ===
+定义森林的权值为每个点度数的平方和，问所有 $n$ 个点构成的带标号森林的权值和。
+=== 题解 ===
+设 $n$ 个点构成的带标号树的个数为 $t_{1,n}$，所有 $n$ 个点构成的带标号树的权值和为 $t_{2,n}$。
+$n$ 个点构成的带标号森林的个数为 $f_{1,n}$，所有 $n$ 个点构成的带标号森林的权值和为 $f_{2,n}$。
+考虑如何递推 $f_{2,n}$。$f_{2,n}$ 可以理解为从其他 $n-1$ 个点中选 $i$ 个与 $n$ 构成一棵树，其余点任意。
+$$f_{2,n}=\sum_{i=0}^{n-1} {n-1\choose i}\left(t_{2,i+1}f_{1,n-1-i}+f_{2,n-1-i}t_{1,i+1}\right)$$
+于是问题转化为求 $t_{1,n},t_{2,n},f_{1,n}$。
+首先根据  $\text{Cayley}$ 公式易知 $t_{1,n}=n^{n-2}$。
+$f_{1,n}$ 可以理解为从其他 $n-1$ 个点中选 $i$ 个与 $n$ 构成一棵树，其余点任意。
+$$f_{1,n}={n-1\choose i}t_{1,i+1}f_{1,n-1-i}$$
+接下来考虑递推 $t_{2,n}$。由于每个点地位等价，可以先计算出每个点在所有方案中的贡献和，最后乘以 $n$。
+于是考虑枚举每个点的度数 $i$，根据 $\text{Prufer}$ 序列性质，有该结点恰好出现 $i-1$ 次，其他节点任意。
+$$t_{2,n}=n\sum_{i=1}^ni^2 {n-2\choose i-1}n^{n-2-i+1}$$
+于是可以 $O(n^2)$ 解决上述问题。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e3+5;
+int C[MAXN][MAXN],tpow[MAXN],t1[MAXN],f1[MAXN],t2[MAXN],f2[MAXN],Mod;
+int quick_pow(int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+int main()
+{
+	int T=read_int();
+	Mod=read_int();
+	_for(i,0,MAXN)
+	C[i][0]=1;
+	_for(i,1,MAXN)_rep(j,1,i)
+	C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
+	t1[0]=t1[1]=1;
+	_for(i,2,MAXN)
+	t1[i]=quick_pow(i,i-2);
+	_for(i,2,MAXN){
+		tpow[0]=1;
+		_for(j,1,i)
+		tpow[j]=1LL*tpow[j-1]*(i-1)%Mod;
+		_for(j,1,i)
+		t2[i]=(t2[i]+1LL*j*j%Mod*C[i-2][j-1]%Mod*tpow[i-1-j])%Mod;
+		t2[i]=1LL*i*t2[i]%Mod;
+	}
+	f1[0]=f1[1]=1;
+	_for(i,2,MAXN)_for(j,0,i)
+	f1[i]=(f1[i]+1LL*t1[j+1]*C[i-1][j]%Mod*f1[i-1-j])%Mod;
+	_for(i,2,MAXN)_for(j,0,i)
+	f2[i]=(f2[i]+(1LL*t1[j+1]*f2[i-1-j]%Mod+1LL*t2[j+1]*f1[i-1-j]%Mod)*C[i-1][j]%Mod)%Mod;
+	while(T--)
+	enter(f2[read_int()]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具