专栏文章

题解：P13020 [GESP202506 八级] 遍历计数

XXCDRF
P13020题解参与者 11已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@mip0fsza
此快照首次捕获于
2025/12/03 04:08
3 个月前
此快照最后确认于
2025/12/03 04:08
3 个月前
查看原文

P13020 [GESP202506 八级] 遍历计数 题解

题目链接
转至专栏阅读

解题思路

题目让我们计算一棵树上所有不同的 DFS 序的数量。将题目转化一下：计算在 DFS 的过程中，每一步有多少种选择，然后将所有选择数相乘。
设 V={1,2,…,n}V = \{1, 2, \dots, n\} 为树的节点集合，Count(s)\text{Count}(s) 为从节点 ss 出发的不同 DFS 序的数量。总数 Total\text{Total} 为：∑s∈VCount(s)\sum_{s \in V} \text{Count}(s)。
先考虑固定起点的情况。对于起点 ss，可以按任意顺序访问相邻节点，也就是有 deg(s)!\text{deg}(s)! 种情况，剩下的点也可以按任意顺序访问相邻节点，但是不能访问父节点，所以有 (deg(u)−1)!(\text{deg}(u)-1)! 种情况。
以该节点为起点的情况数为：
Count(s)=deg(s)!×∏u∈V,u≠s(deg(u)−1)!=deg(s)×∏u∈V(deg(u)−1)!\begin{align*} \text{Count}(s) &= \text{deg}(s)! \times \prod_{u\in V, u \neq s} (\text{deg}(u) - 1)!\\ &= \text{deg}(s) \times \prod_{u\in V} (\text{deg}(u) - 1)!\\ \end{align*}\\
所以总数为：
Total=∑s∈VCount(s)=∑s∈V(deg(s)×∏u∈V(deg(u)−1)!)=∏u∈V(deg(u)−1)!×∑s∈Vdeg(s)\begin{align*} \text{Total} &= \sum_{s \in V} \text{Count}(s) \\ &= \sum_{s\in V} (\text{deg}(s) \times \prod_{u\in V} (\text{deg}(u) - 1)!)\\ &=\prod_{u\in V} (\text{deg}(u) - 1)!\times\sum_{s\in V} \text{deg}(s) \end{align*}
因为所有顶点的度数之和等于边数的两倍。所以在一棵有 nn 个节点的树中： ∑s∈Vdeg(s)=2(n−1)\sum_{s \in V} \text{deg}(s) = 2(n-1)
将此结果代回到原式中，总数为：
Total=∏u∈V(deg(u)−1)!×2(n−1)\text{Total} = \prod_{u\in V} (\text{deg}(u) - 1)! \times 2(n-1)
注意：当 n=1n=1 时，DFS 序数量为 11，需要特判。

参考代码

CPP
#include<iostream>
using namespace std;
const int N=1e5+5,mod=1e9;
int n,ans;
int deg[N],fac[N]={1};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	ans=2*(n-1);
	if(n==1){
		cout<<1;
		return 0;
	}
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		deg[x]++,deg[y]++;
	}
	for(int i=1;i<=n;i++) ans=1ll*ans*fac[deg[i]-1]%mod;
	cout<<ans;
	return 0;
}
AC 记录

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...