列表

详情


NC247066. 233的树

描述

读入一个数n,代表树的点数为n

f(d_1,d_2,...,d_n)代表n个点的度数分别为d_i的情况下,树的直径的最大值(若不能构成树,)

树的直径: 树上距离最远的两点间的距离

树上两点间距离:两点之间路径上的点数(包括自己)

求满足d_i是正整数的情况下,的值,答案对取模

输入描述

第一行一个正整数

输出描述

输出一行一个数代表答案

示例1

输入:

3

输出:

9

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 49ms, 内存消耗: 12100K, 提交时间: 2022-12-09 21:16:45

//233的树
#include<iostream>
using namespace std;
const int mod = 1e9+7 , N = 1e6+10;
int C[N] , D[N] , inv[N];
int main()
{
	int n; cin >> n;
	if(n < 3) 
	{
		cout << n << '\n';
		return 0;
	}
	C[0] = D[0] = inv[0] = inv[1] = 1;
	for(int i = 2 ; i <= n ; ++i)
		inv[i] = (mod - 1ll * inv[mod % i] * (mod / i) % mod) % mod;
	for(int i = 1 ; i <= n ; ++i)
		C[i] = 1ll * C[i-1] * (n - i + 1) % mod * inv[i] % mod;
	for(int i = 1 ; i <= n - 3 ; ++i)
		D[i] = 1ll * D[i-1] * (n - 3 - i + 1) % mod * inv[i] % mod;
	int Ans = 0;
	for(int i = 2 ; i <= n ; ++i)
	{
		Ans = (Ans + 1ll * C[i] * D[n-i-1] % mod * (n - i + 2) % mod) % mod;
	}
	cout << Ans << '\n';
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 267ms, 内存消耗: 8312K, 提交时间: 2022-12-09 22:08:12

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
ll inv(ll x){
	ll y=mod-2,ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
ll jc[maxn],n,ans;
ll C(ll n,ll m){
	return jc[n]*inv(jc[m]*jc[n-m]%mod)%mod;
}
int main(){
	jc[0]=1;for(int i=1;i<maxn;i++) jc[i]=jc[i-1]*i%mod;
	cin>>n;
	if(n<=2){
		cout<<n;
		return 0;
	}
	for(int i=2;i<=n-1;i++){
		ans+=(n-i+2)*C(n,i)%mod*C(n-3,n-i-1)%mod;
	}
	printf("%lld",ans%mod);
} 

上一题