Tính hiệu nCr cho r từ 0 đến n hiệu quả trong Python

Cần tính các giá trị nC0, nC1, ..., nCn nhiều lần. Sử dụng công thức truy hồi: nCr = nC(r-1) * (n - r + 1) / r. Kết quả modulo 10^9 nếu quá lớn.

Ví dụ: n=6 → [1, 6, 15, 20, 15, 6, 1].

Giải thuật

• Khởi tạo items = [1].
• Với r từ 1 đến n:
  • Thêm items[-1] * (n - r + 1) // r vào items.
  • Lấy modulo 10^9 cho phần tử trước cuối (để tránh tràn).
• Trả về items.

Ví dụ mã 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))  # Output: [1, 6, 15, 20, 15, 6, 1]

Đầu vào

6

Đầu ra

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