[Quy hoạch động] [Tổ hợp] [Bao hàm - Loại trừ] [Đường tròn] [Dynamic Programming] [Combinatorics] [Inclusion-Exclusion] [Circle] [AtCoder] AGC028-D Chords

Đề bài

Tóm tắt đề bài

Cho 2N điểm cách đều nhau trên đường tròn và K cặp điểm được nối sẵn, tính tổng của tổng số thành phần liên thông của các cách nối N-K cặp điểm còn lại.

Ý tưởng

Đếm số lần xuất hiện của các thành phần liên thông có i là điểm có chỉ số nhỏ nhất và j là điểm có chỉ số lớn nhất, ta gọi thành phần liên thông như vậy là thành phần (i,j).

Lời giải

Ta có thể sử dụng phương pháp quy hoạch động để tính số loại thành phần (i,j).

Đầu tiên, gọi x là số điểm chưa được nối trong số các điểm có chỉ số từ i đến j, ta thấy số cách nối các điểm này là (x-1)*(x-3)*...*1 (nếu x chẵn, nếu x lẻ thì ta không có cách nối). Tuy nhiên, ta thấy rằng không phải bất cứ cách nối nào cũng cho ta đúng một loại thành phần (i,j) (vì có thể có trường hợp nối thành hai thành phần (i,k) và (k,j) với k nằm giữa i và j). Do đó, ta phải tìm cách loại các trường hợp này ra.

Sau một hồi suy nghĩ, gọi dp(i,j) là số loại thành phần (i,j), ta có công thức quy hoạch động
dp(i,j) = (số cách nối các điểm từ i đến j) - tổng các (dp(i,k) * (số cách nối các điểm từ k đến j)) với k chạy từ i đến j.

Lưu ý rằng đầu tiên ta phải kiểm tra xem có điểm nào nằm giữa i và j nối ra ngoài đoạn từ i đến j không, vì nếu có thì ta không thể có được thành phần (i,j).

Mỗi loại thành phần (i,j) sẽ xuất hiện trong (số cách nối các điểm nằm ngoài đoạn i đến j) cách nối, do đó đáp án sẽ là tổng các (dp(i,j)*(số cách nối các điểm nằm ngoài đoạn i đến j)).

Code (Java)