สมมติว่าเรามีสองรายการ nums1 และ nums2 ตอนนี้ ข้อจำกัดคือเมื่อเรารวมลำดับขององค์ประกอบในแต่ละรายการจะไม่เปลี่ยนแปลง ตัวอย่างเช่น หากองค์ประกอบเป็น [1,2,3] และ [4,5,6] รายการที่ผสานที่ถูกต้องบางรายการคือ [1, 4,2,3,5,6] และ [1,2,3,4,5,6] อาจมีลำดับการผสานที่ถูกต้องอื่นๆ ดังนั้นหากเรามีขนาดของรายการ N และ M เราต้องหาหลายวิธีที่จะรวมเข้าด้วยกันเพื่อให้ได้รายการที่ถูกต้อง หากคำตอบมีขนาดใหญ่เกินไป ผลลัพธ์ที่ได้จะเป็นโมดูโล 10^9 + 7.
ดังนั้น หากอินพุตเป็น N =5 M =3 เอาต์พุตจะเป็น 56
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ret :=1
- สำหรับ i ในช่วง N + 1 ถึง N + M ให้ทำ
- ret :=ret * i
- สำหรับฉันในช่วง 1 ถึง M ให้ทำ
- ret :=ชั้นของ r/i
- รีเทิร์น ret mod (10^9 + 7)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
5, 3
ผลลัพธ์
56
