9.23 T1 tree

题意描述：

给你一个长度为 \(n\) 的序列，让你从中选出 \(k\) 个数组成一个集合，定义这个集合的极限高度为\(a_i...a_k\) 的最大值。

让你求所有的集合极限高度之和对 \(1000000007\) 的结果。

题解：

套路题 OR 水题

我们还是考虑一个数对答案的贡献，就是他作为区间最大值出现的次数。

假设，比 \(x\) 小的数有 \(m\) 个，那么从这 \(m\) 个数中选出 \(k-1\) 个数在和 \(x\) 这个数拼在一起组合成一个集合的最大值就是 \(x\)

选数的方案数为 \(C_{m}^{k-1}\) ,那么 \(x\) 这个数对答案的贡献就是 \(C_{m}^{k-1} \times x\)

先处理一下阶乘以及阶乘的逆元，在计算每个数对答案的贡献即可。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define int long long

const int p = 1e9+7;

const int N = 1e5+10;

int n,k,ans,t;

int h[N],jz[N],inv[N];

inline int read()

{	int s = 0,w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

	return s * w;

}

bool comp(int a,int b)

{

	return a > b;

}

int ksm(int a,int b)

{

	int res = 1;

	for(; b; b >>= 1)

	{

		if(b & 1) res = res * a % p;

		a = a * a % p;

	}

	return res;

}

void YYCH()

{

	jz[0] = inv[0] = 1;

	for(int i = 1; i <= N-5; i++) jz[i] = jz[i-1] * i % p;

	inv[N-5] = ksm(jz[N-5],p-2);

	for(int i = N-6; i >= 1; i--) inv[i] = inv[i+1] * (i+1) % p;

}

int C(int n,int m)

{

	if(n < m) return 0;

	if(n == 0 || m == 0) return 1;

	return jz[n] * inv[n-m] % p * inv[m] % p;

}

signed main()

{

	freopen("trees.in","r",stdin);

	freopen("trees.out","w",stdout);

	n = read(); k = read(); YYCH();

 	for(int i = 1; i <= n; i++) h[i] = read();

	sort(h+1,h+n+1,comp);

	for(int i = 1; i <= n; i++)

	{

		ans = (ans + C(n-i,k-1) * h[i] % p) % p;

	}

	printf("%lld\n",ans % p);

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

9.23 T1 tree

题意描述：

题解：

最新文章

热门文章