2020-2021:teams:legal_string:jxm2001:prufer序列

差别

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

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:prufer序列 [2020/08/16 12:19]
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}$ 序列还原树。
@@ 行 129: / 行 131: @@
 	}
 	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>

2020-2021/teams/legal_string/jxm2001/prufer序列.1597551598.txt.gz · 最后更改: 2020/08/16 12:19 由 jxm2001