题解 | #Y型树#_牛客博客

题目链接

Y型树

题目描述

给定 $n$ 个顶点，你可以用这些顶点构成一棵树。

如果这棵树恰好只有三个叶子节点（度为1的节点），我们称之为“Y型树”。

请问，用这 $n$ 个顶点可以构建出多少种不同的Y型树？

结果需要对 $10^9+7$ 取模。

解题思路

1. 问题解读：有标号 vs. 无标号

虽然题目提到了“顶点”，通常在图论中暗示顶点是带标号的，但题目的样例揭示了问题的本质。

对于 $n=4$ ，如果顶点有标号，我们可以任选一个点作为中心（度为3），剩下3个点作为叶子。这样有 $\binom{4}{1}=4$ 种不同的树。但这与样例输出“1”矛盾。
对于 $n=6$ ，样例输出“2”。

这说明题目实际上是在问，有多少种结构上不同（同构）的Y型树，即这是一个无标号图的计数问题。

2. Y型树的结构与整数划分

一棵有3个叶子的树，其结构必然是由一个度为3的中心节点，连接着三条“臂”（链）构成。
由于我们不关心顶点的标号，只关心树的形态，那么唯一决定Y型树结构的因素就是这三条臂的长度。
$n$ 个顶点中，1个作为中心，剩下 $n-1$ 个顶点分布在这三条臂上。设三条臂的顶点数分别为 $N_1, N_2, N_3$ 。
我们必须有 $N_1+N_2+N_3 = n-1$ ，且 $N_1, N_2, N_3 \ge 1$ (因为每条臂至少要有一个顶点，即叶子节点)。

因此，问题被完美地转化为了一个经典的组合数学问题：将整数 $n-1$ 划分为 3 个正整数之和，有多少种不同的划分方案？

3. 整数划分公式

一个整数 $k$ 划分为 3 个正整数之和的方案数，等价于将 $k-3$ 划分为最多 3 个非负整数之和的方案数。
对于将整数 $k'$ 划分为最多3个部分，有一个著名的近似公式，其精确值为 $\text{round}(\frac{(k'+3)^2}{12})$ 。
在本题中，我们要划分的是 $n-1$ ，所以对应的 $k'$ 是 $(n-1)-3 = n-4$ 。
代入公式，方案数为 $\text{round}(\frac{((n-4)+3)^2}{12}) = \text{round}(\frac{(n-1)^2}{12})$ 。
为了避免浮点数计算，我们可以使用等价的整数算式： $\lfloor \frac{(n-1)^2+6}{12} \rfloor$ ，即 ((n-1)^2 + 6) / 12。

4. 大数处理

$n$ 的范围可达 $10^{18}$ ，所以 $(n-1)^2$ 会溢出标准的64位整型。需要使用__int128 (C++)，BigInteger (Java) 或 Python 的原生大数支持。
计算出划分数（一个整数）之后，再对这个结果取模 $10^9+7$ 。注意，这里是常规除法，不是模逆元。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

// 使用__int128处理大数
// 注意：该类型在某些编译器或在线判题系统中可能不支持
// 在本地GCC/Clang通常是支持的

// 自定义输出函数，因为标准cout不支持__int128
ostream& operator<<(ostream& os, __int128_t value) {
    if (value == 0) return os << "0";
    string s = "";
    bool neg = value < 0;
    if (neg) value = -value;
    while (value > 0) {
        s += (char)(value % 10 + '0');
        value /= 10;
    }
    if(neg) s += '-';
    reverse(s.begin(), s.end());
    return os << s;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n_ll;
    cin >> n_ll;
    
    if (n_ll < 4) {
        cout << 0 << endl;
        return 0;
    }

    __int128_t n = n_ll;
    __int128_t term = n - 1;
    __int128_t result = (term * term + 6) / 12;
    
    long long mod = 1e9 + 7;
    cout << (long long)(result % mod) << endl;

    return 0;
}

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger n = sc.nextBigInteger();
        
        BigInteger four = new BigInteger("4");
        if (n.compareTo(four) < 0) {
            System.out.println(0);
            return;
        }

        BigInteger term = n.subtract(BigInteger.ONE);
        BigInteger termSquared = term.multiply(term);
        BigInteger numerator = termSquared.add(new BigInteger("6"));
        BigInteger denominator = new BigInteger("12");
        
        BigInteger result = numerator.divide(denominator);
        
        BigInteger mod = new BigInteger("1000000007");
        System.out.println(result.mod(mod));
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)

    if n < 4:
        print(0)
        return
        
    term = n - 1
    result = (term * term + 6) // 12
    
    mod = 10**9 + 7
    print(result % mod)

solve()

算法及复杂度

算法：数学 / 整数划分
时间复杂度: $\mathcal{O}(1)$ 。计算过程只涉及几次大数运算，其时间复杂度与 $n$ 的位数（即 $\log n$ ）有关，但通常视为常数时间。
空间复杂度: $\mathcal{O}(1)$ 。