Chương trình tính trung bình các giá trị đặc biệt cho tất cả các hoán vị của danh sách trong Python

Giả sử chúng ta có một danh sách các phần tử, ta có thể tính giá trị S bằng thuật toán sau:

while size of L > 1 is non-zero, do
    a := L[0]
    b := L[1]
    remove L[1]
    L[0] := a + b + a*b
return L[0] mod (10^9 + 7)

Ở đây ta cần tìm trung bình của tất cả các giá trị S được tính từ tất cả các hoán vị có thể của L.

Ví dụ, nếu đầu vào là L = [5,3,4], thì đầu ra sẽ là 119, vì với tất cả các hoán vị của L, giá trị của S đều là 119, nên trung bình cũng là 119.

Giải pháp

Để giải quyết bài toán này, ta thực hiện các bước sau:

• m := 10^9+7
• li := danh sách các x+1 với mọi x trong L
• prod := 1
• Với mỗi i trong li, thực hiện:
  • prod := prod * i
  • prod := prod mod m
• Trả về (prod-1) mod m

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(L):
    m = 10**9+7
    li = [x+1 for x in L]
    prod = 1
    for i in li:
        prod *= i
        prod %= m
    return (prod-1) % m

L = [5,3,4]
print(solve(L))

Đầu vào

[5,3,4]

Đầu ra

119