11876번: PERICA

https://www.acmicpc.net/problem/11876


$O(n(k+\lg n))$

ai(0부터)를 정렬한 뒤
sum(nCk-1*ai)을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000007
int c[100000][50], a[100000], n, k, r;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    sort(a, a + n);
    for (int i = 0; i<n; i++) {
        c[i][0] = 1;
        for (int j = 1; j<k&&j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        r = (r + (long long)c[i][k - 1] * a[i]) % mod;
    }
    printf("%d", r);
    return 0;
}