スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Facebook Hacker Cup 2013 Round 1 A : Card Game

n 個の整数 a_1, a_2, ..., a_n が与えられる。
ここから k 個選んで b_1, b_2, ..., b_k とおく。
n 個から k 個選ぶすべての選び方について max(b_1, b_2, ..., b_k) の和を取った値を mod 1000000007 で求めよ。

・ 1 ≦ k ≦ n ≦ 10^4

解答

とりあえず a_1, ..., a_n を昇順にソートしておく。
k 個取り出した b_1, ..., b_k も並べ替えて b_1 ≦ ... ≦ b_k としておく。

各 i = 1, 2, ..., n に対して、
b_k = a_i となるような選び方は C(i, k-1) だけあり、そういう選び方をしたときは max(b_1,..,b_k) = a_i なので、答えに a_i・C(i, k-1) を足していけばよい。

ソースコード

#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll M=1000000007;

ll fact[10001];

ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

ll modinv(ll a,ll m){
ll x,y;
if(xgcd(a,m,x,y)==1) return (x+m)%m;
return -1;
}

ll nCr(int n,int r){
if(n<r) return 0;
return fact[n]*modinv(fact[r],M)%M*modinv(fact[n-r],M)%M;
}

ll solve(){
int n,k; scanf("%d%d",&n,&k);
static ll a[10000];
rep(i,n) scanf("%lld",a+i);

sort(a,a+n);

ll ans=0;
rep(i,n){
ans+=a[i]*nCr(i,k-1)%M;
ans%=M;
}
return ans;
}

int main(){
fact[0]=1;
rep(i,10000) fact[i+1]=(i+1)*fact[i]%M;

int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case #%d: %lld\n",t,solve());

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。