企业官网建设流程全解析

网站设计师要求,网站首页快照更新快,广州网站公司,商业网络收费标准2025年6月GESP真题及题解(C八级): 遍历计数 题目描述 给定一棵有 nnn 个结点的树 TTT#xff0c;结点依次以 1,2,…,n1,2,\dots,n1,2,…,n 标号。树 TTT 的深度优先遍历序可由以下过程得到#xff1a; 选定深度优先遍历的起点 sss#xff08;1≤s≤n1 \leq s \leq n1≤s≤…2025年6月GESP真题及题解(C八级): 遍历计数题目描述给定一棵有n nn个结点的树T TT结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n标号。树T TT的深度优先遍历序可由以下过程得到选定深度优先遍历的起点s ss1 ≤ s ≤ n 1 \leq s \leq n1≤s≤n当前位置结点即是起点。若当前结点存在未被遍历的相邻结点u uu则遍历u uu也即令当前位置结点为u uu并重复这一步否则回溯。按照遍历结点的顺序依次写下结点编号即可得到一组深度优先遍历序。第一步中起点的选择是任意的并且第二步中遍历相邻结点的顺序也是任意的因此对于同一棵树T TT可能有多组不同的深度优先遍历序。请你求出树T TT有多少组不同的深度优先遍历序。由于答案可能很大你只需要求出答案对10 9 10^9109取模之后的结果。输入格式第一行一个整数n nn表示树T TT的结点数。接下来n − 1 n-1n−1行每行两个正整数u i , v i u_i, v_iui​,vi​表示树T TT中的一条连接结点u i , v i u_i, v_iui​,vi​的边。输出格式输出一行一个整数表示树T TT的不同的深度优先遍历序数量对10 9 10^9109取模的结果。输入输出样例 1输入 14 1 2 2 3 3 4输出 16输入输出样例 2输入 28 1 2 1 3 1 4 2 5 2 6 3 7 3 8输出 2112说明/提示对于40 % 40\%40%的测试点保证1 ≤ n ≤ 8 1 \leq n \leq 81≤n≤8。对于另外20 % 20\%20%的测试点保证给定的树是一条链。对于所有测试点保证1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105。思路分析问题理解题目要求计算一棵树所有可能的深度优先遍历序列的数量其中起点任意且每个节点处访问子节点的顺序任意。关键转化通过分析发现固定起点 s时DFS序列的数量等于树以 s为根时每个节点的子节点数的阶乘的乘积。进一步推导出总数量为$S \left(\prod_{u1}^n (d(u)-1)!\right) \times \sum_{v1}^n d(v)$其中 d(u)是节点 u的度数。算法步骤读取节点数 n若 n1则直接输出 1。读取边并统计每个节点的度数。预计算阶乘数组便于后续直接取值。计算乘积 P ∏ \prod∏(d(u)-1)!。计算总度数之和即 2(n-1)。输出P × sum_deg m o d 10 9 P \times \text{sum\_deg} \bmod 10^9P×sum_degmod109。代码实现#includebits/stdc.husingnamespacestd;constintMOD1000000000;// 取模基数intmain(){intn;scanf(%d,n);// 特判单节点情况if(n1){printf(1\n);return0;}vectorintdeg(n1,0);// 度数数组1‑based// 读入边并统计度数for(inti0;in-1;i){intu,v;scanf(%d%d,u,v);deg[u];deg[v];}// 预计算阶乘最大可能需要 n-1 的阶乘vectorlonglongfact(n1);fact[0]1;// 0! 1for(inti1;in;i){fact[i]fact[i-1]*i%MOD;}// 计算 P ∏ (d(u)-1)!longlongP1;for(inti1;in;i){// 每个节点的度数至少为1因此 deg[i]-1 0PP*fact[deg[i]-1]%MOD;}// 计算总度数之和即 2*(n-1)longlongsum_deg2LL*(n-1);// 最终答案 P * sum_deg mod MODlonglongansP*sum_deg%MOD;printf(%lld\n,ans);return0;}功能分析1.复杂度时间复杂度 O(n)空间复杂度 O(n)。2.注意事项单独处理 n1 的情况避免出现负数下标。使用long long防止中间结果溢出。模数为10 9 10^9109不是质数但只需乘法取模不影响计算。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}