โปรแกรมนับวิธีรวมสองลิสต์โดยคงลำดับเดิมใน Python

มีสองลิสต์ nums1 และ nums2 เมื่อรวมกันลำดับของสมาชิกในแต่ละลิสต์ต้องไม่เปลี่ยนแปลง ต้องการนับจำนวนวิธีการรวมที่เป็นไปได้ หากคำตอบใหญ่ให้โมดุลอ 10^9+7

ตัวอย่าง: N=5, M=3 ผลลัพธ์คือ 56

ขั้นตอนการแก้ปัญหา

จำนวนวิธีคือค่าคอมบิเนชัน C(N+M, N) หรือ C(N+M, M) สามารถคำนวณได้โดย:

1. คำนวณตัวเศษ: คูณตัวเลขจาก N+1 ถึง N+M
2. คำนวณตัวส่วน: แบ่งด้วยแฟกทอเรียลของ M
3. คืนค่าผลลัพธ์โมดุลอ 10^9+7

ตัวอย่างโค้ด Python

def solve(N, M):
    MOD = 10**9 + 7
    ret = 1
    for i in range(N + 1, N + M + 1):
        ret = ret * i % MOD
    for i in range(1, M + 1):
        ret = ret * pow(i, MOD - 2, MOD) % MOD  # ใช้ modular inverse
    return ret

# ทดสอบ
N = 5
M = 3
print(solve(N, M))  # ผลลัพธ์: 56

อินพุตตัวอย่าง

5, 3

เอาต์พุตตัวอย่าง

56