EOJ Monthly 2020.3 D 钢琴演奏家 题解

题目大意

Cuber QQ 有一个多年的弹奏习惯，他弹奏钢琴，同一时刻一定会同时按下 m 个琴键，他喜欢不同音调交织在一起的声音，可是现在不允许了。

可能是因为时间的原因，钢琴不支持琴键并行（音乐带师 Cuber QQ 发明的词汇）了。通俗来说，当 Cuber QQ 同时按下 $m$ 个琴键的时候，钢琴只会发出音调最高的那个琴键的声音。

不甘心的 Cuber QQ 开始尝试每一个 $m$ 键的组合。他会记录下每一次钢琴发出的音调，他会统计所有演奏出的音调之和，为了验证自己有没有算错，他邀请你来帮他再算一遍。

需要注意的是，因为钢琴坏了，所以可能存在相同音调的琴键。

由于这个和可能会很大，你只需要告诉 Cuber QQ 这个和模 $10^9+7$ 的结果是多少。

解题思路

因为只会发出最高的声音，所以我们可以将其从小到大排序。

第$i$位的贡献为他前面的数中取$m-1$个数的组合次数，即$C_{i-1}^{m-1}$，乘上这一位的大小。

即$a[i]*C_{i-1}^{m-1}$。

由高中数学可知，组合数是可以递推的。

就是这样$C_i ^{m-1} = C_{i-1}^{m-1}*\frac{i}{i-(m-1)}$

（傻乎乎的我以为这样就简单的结束了。。

结果一直WA。。人都傻了

（因为不知道除法是不可以同余的。。

比完之后看了看题解。。

逆元是啥，快速幂我不会啊。。

因为除法不能取余，所以我们需要将除法变为乘法，这样就需要逆元了。

完整代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const long long N=1e9+7; 
int a[1000005];

long long slove(long long a,long long b){//快速幂
	long long ans=1;
	while(b){
		if(b&1)	ans=ans*a%N;
		a=a*a%N;
		b>>=1;
	}
	return ans;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1);
		long long ans=a[m],sum=1;
		for(long long i=m+1;i<=n;i++){
			sum=sum*(i-1)%N*slove(i-m,N-2)%N;//逆元
			ans=(ans+(sum*1ll*a[i])%N)%N;
		}
		printf("%lld\n",ans);
	}
	return 0;
}