tuki2501

coci15c5p3.cpp

Nov 29th, 2021
515
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const ll MOD = 1e9 + 7;
  7.  
  8. const int N = 100005;
  9. const int K = 55;
  10.  
  11. ll a[N], mem[N][K];
  12.  
  13. ll comb(ll n, ll k) {
  14.   if (k < 0 || n < 0 || k > n) return 0;
  15.   if (k == 1) return n;
  16.   if (k == 0 || k == n) return 1;
  17.   if (mem[n][k] != -1) return mem[n][k];
  18.   return mem[n][k] = (comb(n - 1, k) + comb(n - 1, k - 1)) % MOD;
  19. }
  20.  
  21. signed main() {
  22.   cin.tie(0)->sync_with_stdio(0);
  23.   memset(mem, -1, sizeof(mem));
  24.   int n, k;
  25.   cin >> n >> k;
  26.   for (int i = 1; i <= n; i++) {
  27.     cin >> a[i];
  28.   }
  29.   sort(a + 1, a + n + 1);
  30.   ll ans = 0, cnt = 0;
  31.   for (int i = 1; i <= n; i++) {
  32.     if (i > 1 && a[i] != a[i - 1]) cnt = 0;
  33.     cnt++;
  34.     if (i < n && a[i] == a[i + 1]) continue;
  35.     for (int j = 1; j <= cnt; j++) {
  36.       ans += ((comb(cnt, j) * comb(i - cnt, k - j)) % MOD * a[i]) % MOD;
  37.       ans %= MOD;
  38.     }
  39.   }
  40.   cout << ans << '\n';
  41. }
RAW Paste Data