# Nhận xét:
## Khi sort lại dãy A tăng dần, phần tử A[i] sẽ là max trong đoạn từ 1 đến i.
## Từ đây ta có ý tưởng như sau:
B1: Sort lại dãy A tăng dần, duy trì 1 biến kết quả ans, ban đầu ans = 0.
B2: Xét mỗi phần tử A[i], khi đó, A[i] sẽ là giá trị của **__C(i-1, k-1)__** dãy con độ dài k (tức là ta
chọn ra k-1 phần tử trong i - 1 phần tử nằm trước i trong dãy A).
Để tính nhanh C(i-1, k-1) trong O(1), ta có thể xây dựng trước mảng f[i] = i! mod P và g[i]
là nghịch đảo mod P của i!. Sau đó sử dụng công thức nCr = n! / r! / (n-r)!.
## Code tính C(n, k) trong O(1), tiền xử lí O(N):
```
int f[N+1];
int g[N+1];
int n, k;
int sqr(long long x) {
return (1ll*x*x )% P;
}
int pow(int a, long long b) {
if (b == 0) return 1;
else
if (b % 2 == 0)
return sqr(pow(a, b/2) % P) % P;
else
return (a*(sqr(pow(a, b/2)%P) % P)) % P;
}
int nd(int x)
{
return pow(x, P-2) % P;
}
int C(int a, int b)
{
int ans = (1ll* f[a] * g[b]) % P;
ans = (1ll*ans * g[a - b] ) % P;
return ans % P;
}
int32_t main() {
input();
cin >> n >> k;
f[0]=g[0]=1;
for (int i=1; i <=N; i++) f[i] = (1ll*f[i-1]*i) % P;
g[N] = nd(f[N]);
for (int i=N-1; i>0; i--) g[i] = 1ll*g[i+1]*(i+1)%P;
cout << C(n, k);
return 0;
}
```
### (Hàm C(int a, int b) các bạn có thể tùy chỉnh theo ý của mình, ở đây mình định nghĩa C(a, b) là tổ hợp chập b của a)
Quay trở lại bài toán, ta thấy A[i] là max của C(i-1, k-1) dãy con độ dài k. Như vậy, A[i] sẽ đóng góp vào kết quả một lượng là A[i] * C(i-1, k-1),
ta tăng biến ans một lượng như vậy.
(*_Chú ý_* : Khi tăng biến ans, ta cần mod 1e9 + 7).
## Code mẫu:
```
#include<bits/stdc++.h>
#define I first
#define II second
#define ci pair<char,int>
#define lg2(n) (31 - __builtin_clz(n))
#define ll long long
#define int ll
using namespace std;
const long long P = 1e9+7;
const int N = 1e6+10;
const long long INF = 1e18;
void input()
{
#define TASKNAME ""
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(TASKNAME".inp","r" )) {
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout); }
}
int f[N+1];
int g[N+1];
int A[N];
int sqr(long long x) {
return (1ll*x*x )% P;
}
int pow(int a, long long b) {
if (b == 0) return 1;
else
if (b % 2 == 0)
return sqr(pow(a, b/2) % P) % P;
else
return (a*(sqr(pow(a, b/2)%P) % P)) % P;
}
int nd(int x)
{
return pow(x, P-2) % P;
}
int C(int a, int b)
{
int ans = (1ll* f[b] * g[a]) % P;
ans = (1ll*ans * g[b-a] ) % P;
return ans % P;
}
int32_t main() {
input();
f[0]=g[0]=1;
int ans=0;
for (int i=1; i <=N; i++) f[i] = (1ll*f[i-1]*i) % P;
g[N] = nd(f[N]);
for (int i=N-1; i>0; i--) g[i] = 1ll*g[i+1]*(i+1)%P;
int n, k;
cin >> n >> k;
int sum = 0;
for (int i=1; i<=n; i++) {
cin >> A[i];
}
sort(A + 1, A + 1 + n);
for (int i=1; i<=n; i++) {
ans += C(k - 1, i - 1) * A[i];
ans %= P;
}
cout << ans << endl;
return 0;
}
```
zt09nguyenducminh
Created at
1 likes