Y型树

[编程题]Y型树

热度指数：310 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出 ${N}$ 个顶点，你可以将这 ${N}$ 个顶点构成一棵树，若这棵树恰好只有三个分叉，那么我们称这种树为 ${Y}$ 树。
现在给出 ${N}$ 个顶点，请你求出可以由这 ${N}$ 个顶点构建的 ${Y}$ 树有多少种？

输入描述:

输入的第一行给出顶点的个数。

输出描述:

由这个顶点构建的树有多少种？，结果对取模。输出取模后的结果。

示例1

输入

输出

说明

示例2

输入

输出

说明

算法知识视频讲解

雀青

发表于 2025-05-28 18:31:43

这个题目的官解比较抽象，我会对其做一个解释。实际上题目所求为p(N-1,3)下文以M代表N-1。这个p(n,k)即代表分拆数 https://oi-wiki.org/math/combinatorics/partition/#%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0 展开全文

丨阿伟丨

发表于 2025-09-18 11:51:53

题目链接 Y型树题目描述给定个顶点，你可以用这些顶点构成一棵树。如果这棵树恰好只有三个叶子节点（度为1的节点），我们称之为“Y型树”。请问，用这个顶点可以构建出多少种不同的Y型树？结果需要对取模。解题思路 1. 问题解读：有标号 vs. 无标号虽然题目提到了“顶点”，通常在展开全文

量子态发圈

发表于 2025-05-29 14:17:21

分拆数：将个数拆分成3份。不会推公式，直接启动。 from math import gcd mod=int(1e9)+7 n=int(input()) n-=1 ans=(n*n+2*gcd(n,3)-3*gcd(n,2))*pow(12,-1,mod)%mod print(ans) 牛客春招刷展开全文