假设我们有 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。
让我们看看以下实现以获得更好的理解 -
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))
4, 3, [5, 7, 9, 11]输出结果
20