10 đ đc r Giải hộ mình câu này với các bạn Hội xuân tại trường năm nay có gian hàng xổ số trúng điểm thưởng. Có N phiếu, mỗi,phiếu có một mặt giống nhau, mặt còn lại ghi một số nguyên không âm ngẫu nhiên. Ban đầu mặt,ghi số được đặt úp xuống mặt bàn. Người chơi được chọn K phiếu bất kỳ và nhận được số điểm,thưởng là số lớn nhất trong K phiếu trên. Hùng rất hào hứng với trò chơi này và muốn biết tổng,điểm thưởng mình được nhận là bao nhiêu nếu Hùng thử hết tất cả các cách chọn.,Gọi S là tổng điểm thưởng được nhận nếu Hùng thử hết tất cả các cách chọn phiếu. Xét ví,dụ với $N=4,~K=2$ và giá trị của các phiếu lần lượt là 6, 7, 6, 5 thì Hùng có 6 cách chọn và tổng,điểm thưởng S là 39, giá trị điểm thưởng của từng cách được cho trong bảng sau:,

Cách,Giá trị của phiếu chọn,Điểm thưởng
"Cách 1: chọn phiếu thứ 1, thứ 2","6, 7",7
"Cách 2: chọn phiếu thứ 1, thứ 3","6, 6",6
"Cách 3: chọn phiếu thứ 1, thứ 4","6, 5",6
"Cách 4: chọn phiếu thứ 2, thứ 3","7, 6",7
"Cách 5: chọn phiếu thứ 2, thứ 4","7,5",7
"Cách 6: chọn phiếu thứ 3, thứ 4","6, 5",6

,Yêu cầu: Hãy viết một chương trình cho biết phần dư khi chia S cho $10^9+7.$,Dữ liệu: Vào từ file văn bản XOSO.INP dòng đầu chứa hai số nguyên N và K. Dòng thứ hai chứa,N số nguyên X,, $(0\leq X_i\leq10^6)$ lần lượt cho biết giá trị của N phiếu.,Kết quả: Ghi ra file văn bản XOSO.OUT trên một dòng là phần dư khi chia S cho $10^9+7.$,Ràng buộc:,30% test ứng với 30% số điểm của bài có $N\leq1000$ và $1\leq K\leq3$,20% test ứng với 20% số điểm của bài có $N\leq25$ và $1\leq K\leq12$,50% test ứng với 50% số điểm của bài có $N\leq100~000$ và $1\leq K\leq50$

Question

10 đ đc r  Giải hộ mình câu này với các bạn Hội xuân tại trường năm nay có gian hàng xổ số trúng điểm thưởng. Có N phiếu, mỗi,phiếu có một mặt giống nhau, mặt còn lại ghi một số nguyên không âm ngẫu nhiên. Ban đầu mặt,ghi số được đặt úp xuống mặt bàn. Người chơi được chọn K phiếu bất kỳ và nhận được số điểm,thưởng là số lớn nhất trong K phiếu trên. Hùng rất hào hứng với trò chơi này và muốn biết tổng,điểm thưởng mình được nhận là bao nhiêu nếu Hùng thử hết tất cả các cách chọn.,Gọi S là tổng điểm thưởng được nhận nếu Hùng thử hết tất cả các cách chọn phiếu. Xét ví,dụ với $N=4,~K=2$ và giá trị của các phiếu lần lượt là 6, 7, 6, 5 thì Hùng có 6 cách chọn và tổng,điểm thưởng S là 39, giá trị điểm thưởng của từng cách được cho trong bảng sau:,

Cách,Giá trị của phiếu chọn,Điểm thưởng
"Cách 1: chọn phiếu thứ 1, thứ 2","6, 7",7
"Cách 2: chọn phiếu thứ 1, thứ 3","6, 6",6
"Cách 3: chọn phiếu thứ 1, thứ 4","6, 5",6
"Cách 4: chọn phiếu thứ 2, thứ 3","7, 6",7
"Cách 5: chọn phiếu thứ 2, thứ 4","7,5",7
"Cách 6: chọn phiếu thứ 3, thứ 4","6, 5",6

,Yêu cầu: Hãy viết một chương trình cho biết phần dư khi chia S cho $10^9+7.$,Dữ liệu: Vào từ file văn bản XOSO.INP dòng đầu chứa hai số nguyên N và K. Dòng thứ hai chứa,N số nguyên X,, $(0\leq X_i\leq10^6)$ lần lượt cho biết giá trị của N phiếu.,Kết quả: Ghi ra file văn bản XOSO.OUT trên một dòng là phần dư khi chia S cho $10^9+7.$,Ràng buộc:,30% test ứng với 30% số điểm của bài có $N\leq1000$ và $1\leq K\leq3$,20% test ứng với 20% số điểm của bài có $N\leq25$ và $1\leq K\leq12$,50% test ứng với 50% số điểm của bài có $N\leq100~000$ và $1\leq K\leq50$

Timi · Accepted Answer

Để giải bài toán này, chúng ta cần tính tổng điểm thưởng S mà Hùng nhận được khi thử hết tất cả các cách chọn K phiếu trong N phiếu. Điểm thưởng của mỗi cách chọn là số lớn nhất trong các phiếu đã chọn.

Dưới đây là phương pháp giải bài toán:

1. **Đọc dữ liệu**: Đầu tiên, chúng ta đọc số N và K từ file `XOSO.INP`, sau đó đọc N giá trị phiếu.

2. **Tính điểm thưởng**: 
   - Sử dụng phương pháp kết hợp để tìm tất cả các cách chọn K phiếu từ N phiếu. 
   - Đối với mỗi cách chọn, chúng ta tìm giá trị lớn nhất trong K phiếu đã chọn và cộng dồn vào tổng điểm S.

3. **Phần dư**: Cuối cùng, chúng ta sẽ tính phần dư của S khi chia cho $10^9 + 7$.

Dưới đây là mã giả cho chương trình này:

```python
from itertools import combinations

def main():
    MOD = 10**9 + 7

# Đọc dữ liệu
    with open("XOSO.INP", "r") as f:
        N, K = map(int, f.readline().strip().split())
        values = list(map(int, f.readline().strip().split()))

# Tính tổng điểm thưởng S
    S = 0
    for combo in combinations(values, K):
        S += max(combo)
        S %= MOD  # Tránh số quá lớn

# Ghi kết quả ra file
    with open("XOSO.OUT", "w") as f:
        f.write(str(S))

if __name__ == "__main__":
    main()
```

### Giải thích mã:
- **Combinations**: Sử dụng thư viện `itertools` để tạo ra tất cả các tổ hợp K từ N phiếu.
- **Max**: Tính giá trị lớn nhất từ mỗi tổ hợp.
- **Modulo**: Áp dụng phép chia phần dư để đảm bảo không vượt quá giới hạn.

### Lưu ý:
- Đối với các trường hợp có N lớn (đến 100,000) và K lớn (đến 50), cần tối ưu hóa hơn, vì việc tính tất cả các tổ hợp sẽ rất tốn thời gian và bộ nhớ. Phương pháp như sử dụng cấu trúc dữ liệu để lưu trữ và tính toán có thể giúp tối ưu hơn.