校招算法笔面试 | 校招笔面试真题-Y型树
题目题目链接
题目链接
Y型树
题目描述
给出 n n n 个顶点，你可以将这些顶点构成一棵树。若这棵树恰恰只有三个分叉（即存在一个点，从这个点出发恰恰有三条不同的路径到叶子节点），那么我们称这种树为Y型树。
现在给出 n n n 个顶点，请你求出可以由这些顶点构建的Y型树有多少种？
输入:
[*]一个整数 n n n，表现顶点的个数
输出:
[*]一个整数，表现可以构建的Y型树的数量（对 1 0 9 + 7 10^9+7 109+7 取模）
解题思路
这是一个数学题目，可以通过以下步骤解决：
[*] 数学推导：
[*]设 n-1 个点分成三组，每组至少一个点
[*]每组点数的和为 n-1（除去分叉点）
[*]最大组的点数不能凌驾 (n-1)/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)
算法及复杂度
[*]算法：数学 + 快速幂
[*]时间复杂度： O ( log n ) \mathcal{O}(\log n) O(logn) - 主要来自快速幂运算
[*]空间复杂度： O ( 1 ) \mathcal{O}(1) O(1) - 只需要常数空间存储变量
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]