Chương trình tìm tổng chênh lệch giữa các phần tử tối đa và tối thiểu từ k quả bóng được chọn ngẫu nhiên từ n quả bóng bằng Python

Giả sử chúng ta có n quả bóng được đánh số bởi một mảng nums, có kích thước là n và nums [i] đại diện cho số quả bóng thứ i. Bây giờ chúng ta có một giá trị k khác. Trong mỗi lượt, chúng ta chọn k quả bóng từ n quả bóng khác nhau và tìm hiệu của các giá trị lớn nhất và nhỏ nhất của k quả bóng và lưu trữ hiệu số trong một bảng. Sau đó đặt k quả bóng này một lần nữa vào chậu đó và chọn lại cho đến khi chúng ta chọn tất cả các lựa chọn có thể. Cuối cùng tìm tổng của tất cả các khác biệt từ bảng. Nếu câu trả lời quá lớn, thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =4 k =3 nums =[5, 7, 9, 11], thì đầu ra sẽ là 20 vì các kết hợp là -

• [5,7,9], hiệu số 9-5 =4
• [5,7,11], chênh lệch 11-5 =6
• [5,9,11], chênh lệch 11-5 =6
• [7,9,11], chênh lệch 11-7 =4

vậy 4 + 6 + 6 + 4 =20.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7
• inv:=một danh sách mới với các phần tử [0, 1]
• đối với tôi trong phạm vi từ 2 đến n, thực hiện
  • chèn (m - tầng của (m / i) * inv [m mod i] mod m) vào cuối inv
• comb_count:=1
• res:=0
• để chọn trong phạm vi k - 1 đến n - 1, thực hiện
  • res:=res + (nums [pick] - nums [n - 1 - pick]) * comb_count mod m
  • res:=res mod m
  • comb_count:=comb_count * (pick + 1) mod m * inv [pick + 2 - k] mod m
• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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
   for pick in range(k - 1, n):
      res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m
      res %= 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))

Đầu vào

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

Đầu ra

20