Pythonでn個のボールからランダムに選択されたk個のボールから最大要素と最小要素の差の合計を見つけるプログラム

配列numsで番号が付けられたn個のボールがあり、そのサイズはnであり、nums[i]はボールiの数を表しているとします。ここで、別の値kがあります。各ターンで、n個の異なるボールからk個のボールを選び、k個のボールの最大値と最小値の差を見つけて、その差をテーブルに保存します。次に、これらのk個のボールを再びそのポットに入れ、可能なすべての選択肢が選択されるまでもう一度ピックします。最後に、表からすべての差の合計を見つけます。答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がn =4 k =3 nums =[5、7、9、11]の場合、組み合わせは-

• [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-（m / i）* inv [m mod i] mod m）のフロアを挿入します
• comb_count：=1
• res：=0
• 範囲k-1からn-1のピックの場合、do
  • 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
• return 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))

入力

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

出力

20