Chương trình tìm số cách chúng ta có thể hợp nhất hai danh sách sao cho thứ tự không thay đổi trong Python

Giả sử chúng ta có hai danh sách nums1 và nums2. Bây giờ, hạn chế là khi chúng ta hợp nhất thứ tự của các phần tử trong mỗi danh sách không thay đổi, ví dụ:nếu các phần tử là [1,2,3] và [4,5,6], thì một số danh sách hợp nhất hợp lệ là [1, 4,2,3,5,6] và [1,2,3,4,5,6], có thể có một số chuỗi hợp nhất hợp lệ khác. Vì vậy, nếu chúng ta có kích thước của danh sách N và M. Chúng ta phải tìm số cách có thể hợp nhất chúng để có được danh sách hợp lệ. Nếu câu trả lời quá lớn, kết quả trả về mô-đun 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là N =5 M =3, thì đầu ra sẽ là 56

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

• ret:=1
• đối với tôi trong phạm vi N + 1 đến N + M, thực hiện
  • ret:=ret * i
• đối với tôi trong phạm vi từ 1 đến M, hãy thực hiện
  • ret:=tầng của r / i
• return ret mod (10 ^ 9 + 7)

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, M):
   ret = 1
   for i in range(N + 1, N + M + 1):
      ret *= i
   for i in range(1, M + 1):
      ret //= i
   return ret % (10**9 + 7)

N = 5
M = 3
print(solve(N, M))

Đầu vào

5, 3

Đầu ra

56