Tổng hiệu max-min của tất cả tổ hợp k phần tử từ n quả cầu trong Python

Cho n quả cầu đánh số bởi mảng nums (kích thước n). Mỗi lần chọn k quả cầu, tính hiệu giữa max và min của k quả cầu đó, lưu vào bảng. Lặp lại cho tất cả các tổ hợp chọn k từ n. Tính tổng tất cả hiệu đó, modulo 10^9+7.

Ví dụ: n=4, k=3, nums=[5,7,9,11]. Các tổ hợp:

• [5,7,9] → 9-5=4
• [5,7,11] → 11-5=6
• [5,9,11] → 11-5=6
• [7,9,11] → 11-7=4

Giải thuật

• Sắp xếp mảng nums.
• Tính trước nghịch đảo modulo để tính tổ hợp nhanh.
• Duyệt pick từ k-1 đến n-1, cộng dồn (nums[pick] - nums[n-1-pick]) * C(pick, k-1).
• Trả về kết quả modulo 10^9+7.

Ví dụ mã Python

def solve(n, k, nums):
    m = 10**9 + 7
    inv = [0, 1]
    for i in range(2, n + 1):
        inv.append(m - m // i * inv[m % i] % m)
    comb_count = 1
    res = 0
    nums.sort()
    for pick in range(k - 1, n):
        res = (res + (nums[pick] - nums[n - 1 - pick]) * comb_count) % m
        comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m
    return res

n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))  # Output: 20

Đầu vào

4, 3, [5, 7, 9, 11]

Đầu ra

20