โปรแกรมคำนวณค่า nCr สำหรับ r=0 ถึง n อย่างมีประสิทธิภาพใน Python

ต้องการคำนวณค่า nCr สำหรับ r = 0,1,...,n อย่างรวดเร็วโดยใช้ความสัมพันธ์แบบเวียนเกิด: nCr = nC(r-1) * (n-r+1) / r หากคำตอบใหญ่ให้โมดุลอ 10^9

ตัวอย่าง: n=6 ผลลัพธ์: [1, 6, 15, 20, 15, 6, 1]

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

1. เริ่มต้นลิสต์ items = [1] (ค่า nC0)
2. วนลูป r จาก 1 ถึง n:
   • คำนวณค่าถัดไป: items[-1] * (n - r + 1) // r
   • เพิ่มลงใน items
   • ทำโมดุลอ 10^9 กับค่าที่สองจากท้าย (items[-2]) เพื่อป้องกันค่าใหญ่เกิน
3. คืนค่า items

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

def solve(n):
    items = [1]
    for r in range(1, n + 1):
        items.append(items[-1] * (n - r + 1) // r)
        items[-2] %= 10**9
    return items

# ทดสอบ
n = 6
print(solve(n))  # ผลลัพธ์: [1, 6, 15, 20, 15, 6, 1]

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

6

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

[1, 6, 15, 20, 15, 6, 1]