Câu trong ảnh làm như nào các bạn ơi... 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

Câu trong ảnh làm như nào các bạn ơi... 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$

Accepted Answer

Để giải quyết bài toán này, bạn cần xây dựng một chương trình để tính tổng điểm thưởng $ S $ khi Hùng thử hết tất cả các cách chọn $ K $ phiếu từ $ N $ phiếu đã cho. Dưới đây là hướng dẫn từng bước:

1. **Đọc dữ liệu đầu vào**: Bạn cần đọc hai số nguyên $ N $ và $ K $ từ dòng đầu tiên và dãy số nguyên $ X $ từ dòng thứ hai.

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

3. **Xử lý phần dư**: Vì yêu cầu kết quả là phần dư khi chia cho $ 10^9 + 7 $, bạn cần sử dụng phép toán modulo để đảm bảo giá trị không vượt quá giới hạn.

4. **Ghi kết quả ra file**: Cuối cùng, ghi giá trị của $ S $ vào file đầu ra.

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

```python
import itertools

def main():
    MOD = 10**9 + 7
    # Đọc dữ liệu từ file XOSO.INP
    with open(&#x27;XOSO.INP&#x27;, &#x27;r&#x27;) as f:
        N, K = map(int, f.readline().split())
        X = list(map(int, f.readline().split()))
    
    S = 0
    
    # Tạo tất cả các tổ hợp của K phiếu
    for combination in itertools.combinations(X, K):
        S += max(combination)
        S %= MOD  # Lấy phần dư tại mỗi bước
    
    # Ghi kết quả ra file XOSO.OUT
    with open(&#x27;XOSO.OUT&#x27;, &#x27;w&#x27;) as f:
        f.write(str(S))

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

### Giải thích mã:
- **import itertools**: Thư viện này giúp tạo ra các tổ hợp một cách dễ dàng.
- **main()**: Hàm chính, nơi thực hiện toàn bộ logic.
- **itertools.combinations(X, K)**: Tạo ra tất cả các tổ hợp của $ K $ phần tử từ danh sách $ X $.
- **max(combination)**: Tìm số lớn nhất trong tổ hợp.
- **S += max(combination)**: Cộng giá trị lớn nhất vào tổng.
- **S %= MOD**: Đảm bảo giá trị tổng không vượt quá $ 10^9 + 7 $.
- Cuối cùng, kết quả được ghi ra file.

### Lưu ý:
Đảm bảo bạn đã cài đặt Python và tạo file `XOSO.INP` với định dạng dữ liệu như đã mô tả trước khi chạy mã.