Bình luận

• 
  

  2

  

  YougiTuber  đã bình luận lúc 8, Tháng 12, 2025, 22:11 ← chỉnh sửa →

  Spoil⚠️

  Cách tính giá trị kỳ vọng trong bài này

  ~P~ là tập các hoán vị thỏa mãn yêu cầu màu sắc.

  Các hoán vị cần chọn là hoán vị sao cho mọi ~C(i) = C(p_i)~

  => ~P~ là tích của tất cả các ~cnt_c!~

  ~p(A)~ là xác suất để hoán vị ~A~ được chọn, và ~X(A)~ là chi phí đổi nhà theo hoán vị ~A~.

  Vì mọi hoán vị có xác suất được chọn là như nhau, vì vậy giá trị kỳ vọng ~E~ sẽ bằng tổng của mọi ~X(A)~ chia cho ~P~ là số lượng hoán vị thỏa mãn

  ~E = \frac{\sum(X(A))}{\prod_{c=1}^{\infty} cnt_c!}~

  Tính kết quả bằng nghịch đảo modulo

  Các subtask

  Subtask ~1~ (~n \le 10~):

  Sinh tất cả hoán vị, điều kiện hoán vị thỏa mãn là ~C_i = C_{p_i}~

  Với hoán vị thỏa mãn ta sẽ tính chi phí của hoán vị này, bằng tổng chi phí của việc di chuyển từ đỉnh ~i~ sang đỉnh ~p_i~

  Độ phức tạp ~O(2^n + n^2)~

  Subtask ~2~ (Mỗi ngôi nhà có một ngôi nhà khác cùng màu):

  Trong ~50\%~ số hoán vị, thì ~2~ người sẽ chuyển nhà, và ~50\%~ số hoán vị còn lại thì ~2~ người không chuyển nhà, tính trung bình thì giá trị của ~X(A)~ sẽ tăng ~2~ lần khoảng cách và ~0~ lần khoảng cách giữa ~2~ ngôi nhà.

  Vì vậy kết quả của subtask này là tổng khoảng cách giữa mọi cặp nhà cùng màu.

  Độ phức tạp ~O(n^2)~

  Subtask ~3~ (~n \le 1000~):

  Xử lý theo từng màu (nên đọc Subtask ~4~ trước)

  Đối với màu ~c~, nếu như hoán vị toàn bộ là màu ~c~, thì giá trị kỳ vọng sẽ là sẽ là tổng khoảng cách giữa mọi cặp đỉnh màu ~c~ này.

  Nếu giờ thêm màu ~c_1~ vào, với một hoán vị ~p~ của màu ~c~ với đang có giá trị là ~X(p(c))~, thì xác suất xảy ra được hoán vị ~p~ này giờ sẽ phải chia cho ~cnt_{c_1}!~ lần, tương tự chúng ta thêm các màu ~c_2, c_3, ..., c_k~ vào thì ta cần chia nó cho ~cnt_{c_2}!, cnt_{c_3}!, ..., cnt_{c_k}!~, với ~c_i~ khác màu ~c~ hiện tại đang xét.

  Như vậy để tính giá trị kỳ vọng cho bài này, ta sẽ tính bằng

  ~ans = \sum_{c=1}^{\infty}{X(c)}~

  Với ~X(c)~ là tổng giá trị kỳ vọng của việc di chuyển giữa mọi cặp nhà cùng màu ~c~

  ~X(c) = \frac{sum\_dist(c)}{\prod_{c'=0, c'\ne c}^{\infty}cnt_{c'}!}~

  Để dễ hiểu thì tử số ~sum\_dist(c)~ là tổng khoảng cách giữa mọi cặp ~(u, v)~ cùng màu ~c~

  Mẫu số thì có thể tính bằng ~\frac{P}{cnt_c!}~

  ~P = {\prod_{c=0}^{\infty} cnt_c!} = cnt_1! \cdot cnt_2! \cdot ... cnt_{\infty}!~.

  Subtask ~4~ (Tất cả các đỉnh cùng màu):

  Bài toán quy về tính tổng khoảng cách giữa mọi đỉnh cùng màu.

  Để đỉnh ~u~ di chuyển qua đỉnh ~v~ thì ~a_u = v~. Sẽ có ~(n-1)!~ hoán vị đạt được điều này (cố định ~a_u = v~, ~n-1~ số còn lại hoán vị ngẫu nhiên)

  Như vậy kết quả sẽ là ~sum\_dist~ mọi cặp đỉnh, nhân ~(n-1)!~ sau đó chia cho tổng số hoán vị là ~n!~, hay kết quả chính là ~\frac{sum\_dist}{n}~.

  Có ~3~ cách xử lý bằng dp tree

  Cách ~1~:

  Với mỗi cạnh, tính số lượng cặp đỉnh đi qua cạnh đó

  Cạnh ~\{u, v\}~, ~u~ là cha ~v~ thì số cặp đi qua là ~sz[v] \cdot (n - sz[v])~

  Cách ~2~:

  Làm giống bài CSES. Tree Distances II, tính mảng ~dp\_down[u]~ và ~dp\_up[u]~ là tổng khoảng cách từ đỉnh ~u~ đến tất cả các đỉnh bên trong và bên ngoài cây con gốc ~u~, sau đó tính tổng lại.

  Cách ~3~:

  Chỉ cần tính ~dp[u]~ là khoảng cách từ ~u~ đến mọi đỉnh thuộc cây con gốc ~u~, xét một cặp ~u, v~ với ~v~ thuộc cây con gốc ~u~, thay vì cần tính khoảng cách từ ~v~ đến ~u~ một lần nữa, ta chỉ cần nhân ~2~ lần ~dp[u]~ lên để được ~2~ chiều khoảng cách từ ~u~ đến ~v~ và từ ~v~ đến ~u~

  Subtask ~5~ (Không có giới hạn gì thêm):

  Kết hợp việc tính giá trị kỳ vọng của hoán vị theo từng màu (subtask ~3~), và tổng khoảng cách của mọi đỉnh cùng màu (subtask ~4~), lưu ý với subtask ~5~ này thì cạnh giữa ~2~ đỉnh cùng màu sẽ có trọng số bằng khoảng cách giữa chúng.

  Để tính tổng khoảng cách của mọi đỉnh cùng màu, có thể sử dụng:

  • Virtual tree

  • Small to large

  Code tham khảo (Subtask ~1~ - ~4~):

  olp_sc24_newhome.cpp