用 Python 编写程序，从 n 个球中随机选择 k 个球，求出最大和最小元素之间的差异之和

pythonserver side programmingprogramming更新于 2026/2/1 3:56:17

假设我们有 n 个球，它们由数组 nums 编号，数组大小为 n，nums[i] 表示球 i 的编号。现在我们有另一个值 k。每次我们从 n 个不同的球中挑选 k 个球，找出 k 个球的最大值和最小值的差异，并将差异存储在表中。然后将这 k 个球再次放入那个罐子中，再次挑选，直到我们选出所有可能的选择。最后从表中找出所有差异之和。如果答案太大，则返回结果 mod 10^9+7。

因此，如果输入为 n = 4 k = 3 nums = [5, 7, 9, 11]，则输出将为 20，因为组合是 −

[5,7,9]，差 9-5 = 4
[5,7,11]，差 11-5 = 6
[5,9,11]，差 11-5 = 6
[7,9,11]，差 11-7 = 4

所以 4+6+6+4 = 20。

为了解决这个问题，我们将按照以下步骤 −

m := 10^9 + 7
inv := 一个包含元素 [0, 1] 的新列表
对于范围在 2 到 n 内的 i，执行
- 在 inv 末尾插入 (m - floor of (m / i) * inv[m mod i] mod m)
comb_count := 1
res := 0
对于范围在 k - 1 到 n - 1 内的 pick，执行
- 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米
返回 res

示例

让我们看看下面的实现以便更好地理解 −

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))