Số cách trộn hai danh sách giữ nguyên thứ tự trong Python

Cho hai danh sách kích thước N và M. Trộn chúng sao cho thứ tự phần tử trong mỗi danh sách không thay đổi. Đếm số cách trộn hợp lệ, modulo 10^9+7.

Ví dụ: N=5, M=3 → kết quả 56 (tổ hợp C(8,3) hoặc C(8,5)).

Giải thuật

• Kết quả là tổ hợp C(N+M, N) hoặc C(N+M, M).
• Tính bằng cách nhân từ N+1 đến N+M, sau đó chia cho giai thừa M.
• Trả về kết quả modulo 10^9+7.

Ví dụ mã Python

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))  # Output: 56

Đầu vào

5, 3

Đầu ra

56