Atcoder Beginner Contest151E（排列组合）

排列组合

 #define HAVE_STRUCT_TIMESPEC

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 const long long mod = 1e9+;

 long long inv[];

 long long qpow(int p,int q){

     long long s=;

     for(;q;q>>=,p=1ll*p*p%mod)

         if(q&)

             s=1ll*s*p%mod;

     return s;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     int n,k;

     cin>>n>>k;

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

         cin>>a[i];

     sort(a+,a++n);

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

         inv[i]=qpow(i,mod-);

     long long sum=;

     long long temp=;

     for(int i=k;i<=n;++i){

         sum=(sum+a[i]*temp%mod)%mod;

         temp=temp*i%mod;

         temp=temp*inv[i+-k]%mod;

     }

     temp=;

     for(int i=n-k+;i;--i){

         sum=(sum+mod-a[i]*temp%mod)%mod;

         temp=temp*(n-i+)%mod;

         temp=temp*inv[n-i+-k]%mod;

     }

     cout<<sum;

     return ;

 }