[Practice Mode] HackerCup-2013 Round-1 :: CardGame

Lession-1: Don't rush...Keep calm and settle down when you know the logic already.

Lession-2: 1,000,000,007 Is a Magic Number :P and Do Not IGNORE it.

Lession-3: Remember the Rule when working with Modulus Operation, "Apply mod before the result".
If you wait until the result to be computed, answers will be tossed away.

(a+b)mod m = (a mod m + b mod m) mod m;
(a*b)mod m = (a mod m * b mod m) mod m; 

Lession-4: Arrays are the Most beautiful data structure that you ever seen :D. Do not hesitate to use them to compute nCr and etc.

Lession-5: Every problem will have simple solution. Think smart not Bigger.

Lession-6: If you see a Modulus, be ready to solve it. Because modulo randomization always periodical. So Gear up.

// =====================================================================================
//       Filename:  cardGame.cpp
//    Description:  
//        Created:  02/02/2013 11:44:39 PM
//         Author:  BrOkEN@!
// =====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>


#define TIMER 1
#define NMAX 10001
#define MOD 1000000007L

#define FOR(i,a,b) for( typeof(a) i=(a); i < (b) ; ++i )

using namespace std;

int N=0,K=0;
long a[NMAX];
long nCr[NMAX][NMAX];


long solve(){
 sort(a,a+N);
 long sum=0L;K--;
 FOR(i,K,N){
  sum+=(a[i]%MOD * nCr[i][K]%MOD)%MOD;
 }
 return sum%MOD;
}

void preCompute(){
 FOR(i,0,NMAX){
  FOR(j,0,i+1){
   if(j==0) nCr[i][j]=1%MOD;
   else nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%MOD;
  }
 }
}

int main(){
 clock_t t=clock();
 preCompute();
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%d %d",&N,&K);
  for(int i=0;i<N;i++){scanf("%ld",&a[i]);};
  printf("Case #%d: %ld\n",t,solve()); 
 } 
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}