题目链接

Y型树

题目描述

给出 个顶点，你可以将这些顶点构成一棵树。若这棵树恰好只有三个分叉（即存在一个点，从这个点出发恰好有三条不同的路径到叶子节点），那么我们称这种树为Y型树。

现在给出 个顶点，请你求出可以由这些顶点构建的Y型树有多少种？

输入:

  • 一个整数 ，表示顶点的个数

输出:

  • 一个整数，表示可以构建的Y型树的数量（对 取模）

解题思路

这是一个数学问题，可以通过以下步骤解决：

  1. 数学推导：

    • 设 n-1 个点分成三组，每组至少一个点
    • 每组点数的和为 n-1（除去分叉点）
    • 最大组的点数不能超过 (n-1)/3

  2. 计算策略：

    • 使用等差数列求和公式计算部分结果
    • 通过快速幂计算逆元
    • 使用补集的思想避免复杂的组合数计算

  3. 具体步骤：

    • 计算 k = (n-1)/3
    • 使用 sum 函数计算等差数列的和
    • 使用 calc 函数处理特殊情况
    • 最终结果通过几个部分相加得到

代码

#include <iostream>
using namespace std;
using ll = long long;
const int mod = 1000000007;

ll modpow(ll a, ll b) {
    ll res = 1 % mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll sum(ll x) {
    x %= mod;
    return x % mod * (x + 1) % mod * modpow(2, mod-2) % mod;
}

ll calc(ll x) {
    ll ret = sum(x/2) * 2 % mod;
    if(x % 2 == 0) ret += mod - x/2 % mod, ret %= mod;
    return ret;
}

int main() {
    ll n;
    cin >> n;
    n--;  // 除去分叉点
    ll k = n/3;  // 最大组的点数
    ll ans = 0;
    ans += calc(n-1) + mod - calc(n-k-1), ans %= mod;
    ans += mod - sum(k) % mod, ans %= mod;
    ans += k, ans %= mod;
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    static long modpow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    static long sum(long x) {
        x %= MOD;
        return x % MOD * (x + 1) % MOD * modpow(2, MOD-2) % MOD;
    }
    
    static long calc(long x) {
        long ret = sum(x/2) * 2 % MOD;
        if(x % 2 == 0) ret = (ret + MOD - x/2 % MOD) % MOD;
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        n--;  // 除去分叉点
        long k = n/3;  // 最大组的点数
        long ans = 0;
        ans = (ans + calc(n-1) + MOD - calc(n-k-1)) % MOD;
        ans = (ans + MOD - sum(k) % MOD) % MOD;
        ans = (ans + k) % MOD;
        System.out.println(ans);
    }
}

def modpow(a, b, mod):
    return pow(a, b, mod)

def sum_mod(x, mod):
    x %= mod
    return x * (x + 1) % mod * modpow(2, mod-2, mod) % mod

def calc(x, mod):
    ret = sum_mod(x//2, mod) * 2 % mod
    if x % 2 == 0:
        ret = (ret + mod - x//2 % mod) % mod
    return ret

MOD = 10**9 + 7
n = int(input())
n -= 1  # 除去分叉点
k = n//3  # 最大组的点数

ans = 0
ans = (ans + calc(n-1, MOD) + MOD - calc(n-k-1, MOD)) % MOD
ans = (ans + MOD - sum_mod(k, MOD)) % MOD
ans = (ans + k) % MOD

print(ans)

算法及复杂度

  • 算法：数学 + 快速幂
  • 时间复杂度： - 主要来自快速幂运算
  • 空间复杂度： - 只需要常数空间存储变量