https://atcoder.jp/contests/abc151/tasks/abc151_e
给出n个数,从中任选k个数,记f=这k个数最大值-最小值
求所有的f的和
Σ(max-min)=Σmax-Σmin
计算每个数成为max,min有多少种可能
将n个数从小到大排序后,第i个数 是max的选法有C(i-1,k-1)种,同理可算第i个数是min的选法方案
#include<cstdio> #include<algorithm> using namespace std; #define N 100001 const int mod=1e9+7; int a[N],inv[N]; int Pow(int p,int q) { int s=1; for(;q;q>>=1,p=1LL*p*p%mod) if(q&1) s=1LL*s*p%mod; return s; } int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<=n;++i) inv[i]=Pow(i,mod-2); long long p=1,ans=a[k]; for(int i=k+1;i<=n;++i) { p=p*(i-1)%mod; p=p*inv[i-k]%mod; ans=(ans+a[i]*p%mod)%mod; } ans-=a[n-k+1]; p=1; for(int i=k+1;i<=n;++i) { p=p*(i-1)%mod; p=p*inv[i-k]%mod; ans=(ans-a[n-i+1]*p%mod)%mod; } if(ans<0) ans+=mod; printf("%d",ans); }