โปรแกรมหาผลรวมความต่างระหว่างค่าสูงสุดและต่ำสุดจากการเลือก k ลูกบอลจาก n ลูกใน Python

มี n ลูกบอล หมายเลขตามอาร์เรย์ nums (ขนาด n) เลือก k ลูกบอลทุกคอมบิเนชันที่เป็นไปได้ หาความต่างระหว่างค่าสูงสุดและต่ำสุดของแต่ละคอมบิเนชัน แล้วนำมารวมกัน หากคำตอบใหญ่เกินให้โมดูลอ 10^9+7

ตัวอย่าง: n=4, k=3, nums=[5,7,9,11] คอมบิเนชันและความต่าง: [5,7,9]→4, [5,7,11]→6, [5,9,11]→6, [7,9,11]→4 ผลรวม = 20

ขั้นตอนการแก้ปัญหา

1. เรียงลำดับ nums จากน้อยไปมาก
2. คำนวณ modular inverse ล่วงหน้าสำหรับการคำนวณคอมบิเนชัน
3. ใช้สูตร: ผลรวมสำหรับ pick จาก k-1 ถึง n-1 ของ (nums[pick] - nums[n-1-pick]) * C(pick, k-1) แล้วโมดูลอ

ตัวอย่างโค้ด Python

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

# ทดสอบ
n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))  # ผลลัพธ์: 20

อินพุตตัวอย่าง

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

เอาต์พุตตัวอย่าง

20