EOJ Monthly 2020.3 D. 钢琴演奏家

2023-09-24 12:12:58

Cuber QQ 在疫情期间已经宅在家两个月了。

实在是无所事事的他，决定重操旧业，继续实现他曾经梦寐的钢琴演奏家梦想。

掀开积满了灰尘的钢琴盖，是他许久都未触碰的琴键，按下的瞬间，他发现，钢琴坏了。

Cuber QQ 有一个多年的弹奏习惯，他弹奏钢琴，同一时刻一定会同时按下 m 个琴键，他喜欢不同音调交织在一起的声音，可是现在不允许了。

可能是因为时间的原因，钢琴不支持琴键并行（音乐带师 Cuber QQ 发明的词汇）了。通俗来说，当 Cuber QQ 同时按下 m 个琴键的时候，钢琴只会发出音调最高的那个琴键的声音。

不甘心的 Cuber QQ 开始尝试每一个 m 键的组合。他会记录下每一次钢琴发出的音调，他会统计所有演奏出的音调之和，为了验证自己有没有算错，他邀请你来帮他再算一遍。

需要注意的是，因为钢琴坏了，所以可能存在相同音调的琴键。

由于这个和可能会很大，你只需要告诉 Cuber QQ 这个和模 109+7 的结果是多少。

输入格式

输入数据第一行包含一个整数 T (1≤T≤1000) 表示数据组数。

对于每一组数据，第一行包含两个整数 n, m (1≤m≤n≤106) ，分表表示钢琴的琴键数量和每次同时按下的琴键个数。

第二行包含 n 个整数 a1,a2,…,an (0≤ai≤109)，表示琴键的音调（可能会出现相同的音调）。

保证对于所有数据有 ∑n≤106 。

输出格式

对于每组数据输出一行，包含一个整数表示答案。

由于答案可能很大，需要对 109+7 取模。

样例

input

1
3 2
1 2 3

output

// CF练习.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#include <xfunctional>
using namespace std;
int dir[4][2] = { { 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979;
using ll = long long;
using PII = pair<int, int>;
const int mod = 1e9 + 7;
const int maxn = 1000000 + 5;

inline int add(int x, int y) {
    x += y;
    return x >= mod ? x -= mod : x;
}
inline int sub(int x, int y) {
    x -= y;
    return x < 0 ? x += mod : x;
}
inline int mul(int x, int y) {
    return 1ll * x * y % mod;
}
inline int qpow(int x, ll n) {
    int r = 1;
    while (n > 0) {
        if (n & 1) r = 1ll * r * x % mod;
        n >>= 1; x = 1ll * x * x % mod;
    }
    return r;
}
inline int Inv(int x) {
    return qpow(x, mod - 2);
}

namespace Comb {
    const int maxc = 2000000 + 5;
    int f[maxc], inv[maxc], finv[maxc];
    void init() 
    {
        inv[1] = 1;
        for (int i = 2; i < maxc; i++)
            inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
        f[0] = finv[0] = 1;
        for (int i = 1; i < maxc; i++)
        {
            f[i] = f[i - 1] * 1ll * i % mod;
            finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
        }
    }
    int C(int n, int m)
    {
        if (m < 0 || m > n) return 0;
        return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
    }
    int S(int n, int m)
    {
        // x_1 + x_2 + ... + x_n = m, x_i >= 0
        if (n == 0 && m == 0) return 1;
        return C(m + n - 1, n - 1);
    }
}
using Comb::C;
int n, m, a[maxn];

int main() {
    Comb::init();
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        sort(a + 1, a + 1 + n);
        int ans = 0;
        for (int i = m; i <= n; i++) {
            int tot = mul(C(i - 1, m - 1), a[i]);
            ans = add(ans, tot);
        }
        printf("%d\n", ans);
    }
    
    return 0;
}

码农公寓

输入格式

输出格式

样例

相关文章