Codeforces - 1462E2 - Close Tuples (hard version)
★ Today's tune: https://youtu.be/TLVK0iTDev0
★ Tags: binary search, combinatorics, modulo inverse
★ Difficulty: 1700
★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu):
Cho dãy a[] gồm N số. Yêu cầu đếm số cách để chọn ra một dãy có m phần tử, và chênh lệch giữa số lớn nhất và số nhỏ nhất trong dãy tìm được nhỏ hơn hoặc bằng k, lấy dư với 10^9 + 7.
★ Nhận xét: Dãy tìm được không mất tính tổng quát khi so sánh giá trị giữa phần tử lớn nhất và nhỏ nhất trong dãy.
Ví dụ: giả sử chọn được 3 số a[1], a[2], a[3] và a[1] là số lớn nhất, a[3] là số nhỏ nhất. Từ đó suy ra max(a[1], a[2], a[3]) = a[1] và min(a[1], a[2], a[3]) = a[3]. Nếu thay đổi vị trí 3 số này trở thành a[2], a[3], a[1] thì số lớn nhất vẫn là a[1] và số nhỏ nhất vẫn là a[3] -> không đổi.
Suy ra dãy cần tìm không bị ràng buộc theo thứ tự vị trí. Ta chỉ cần đếm cách chọn m số trong đoạn từ [x, x + k]. Có thể sắp xếp lại và dùng tổ hợp để tính bằng cách cố định số a[i] và chọn m - 1 số trong dãy còn lại.
Đầu tiên ta sẽ sắp xếp lại dãy a[] theo thứ tự tăng dần -> với mỗi phần tử a[i] sẽ tìm phần tử ở xa nhất có giá trị là a[i] + k + 1 bằng tìm kiếm nhị phân -> độ dài của dãy tìm được chính là r - l (với l = i, r = vị trí của số a[i] + k + 1 trong mảng).
Công thức tổ hợp: Ckn = n! / [(n - k)! * k!]
Công thức áp dụng: thay n = r - l, và k = m - 1 vào công thức trên.
★ Lưu ý:
- Với n! có thể tính trước.
- Với (n - k)! và k! có thể tính trước nhưng sử dụng nghịch đảo modulo.
★ Code: https://ideone.com/1ssMV0
★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu):
Cho dãy a[] gồm N số. Yêu cầu đếm số cách để chọn ra một dãy có m phần tử, và chênh lệch giữa số lớn nhất và số nhỏ nhất trong dãy tìm được nhỏ hơn hoặc bằng k, lấy dư với 10^9 + 7.
★ Nhận xét: Dãy tìm được không mất tính tổng quát khi so sánh giá trị giữa phần tử lớn nhất và nhỏ nhất trong dãy.
Ví dụ: giả sử chọn được 3 số a[1], a[2], a[3] và a[1] là số lớn nhất, a[3] là số nhỏ nhất. Từ đó suy ra max(a[1], a[2], a[3]) = a[1] và min(a[1], a[2], a[3]) = a[3]. Nếu thay đổi vị trí 3 số này trở thành a[2], a[3], a[1] thì số lớn nhất vẫn là a[1] và số nhỏ nhất vẫn là a[3] -> không đổi.
Suy ra dãy cần tìm không bị ràng buộc theo thứ tự vị trí. Ta chỉ cần đếm cách chọn m số trong đoạn từ [x, x + k]. Có thể sắp xếp lại và dùng tổ hợp để tính bằng cách cố định số a[i] và chọn m - 1 số trong dãy còn lại.
Đầu tiên ta sẽ sắp xếp lại dãy a[] theo thứ tự tăng dần -> với mỗi phần tử a[i] sẽ tìm phần tử ở xa nhất có giá trị là a[i] + k + 1 bằng tìm kiếm nhị phân -> độ dài của dãy tìm được chính là r - l (với l = i, r = vị trí của số a[i] + k + 1 trong mảng).
Công thức tổ hợp: Ckn = n! / [(n - k)! * k!]
Công thức áp dụng: thay n = r - l, và k = m - 1 vào công thức trên.
★ Lưu ý:
- Với n! có thể tính trước.
- Với (n - k)! và k! có thể tính trước nhưng sử dụng nghịch đảo modulo.
★ Code: https://ideone.com/1ssMV0
Comments
Post a Comment