type
status
date
slug
summary
tags
category
icon
password
Bài viết này sẽ giới thiệu một số insight mình có được khi thực hành áp dụng SOS DP, sau khi học từ VNOI. Về kĩ thuật này, VNOI Wiki đã khá đầy đủ và chi tiết để áp dụng được từ các bài tập dễ đến trung bình khó.
SOS là một kĩ thuật mạnh, và đặc biệt hiệu quả trong các bài toán đếm tổ hợp và bao hàm loại trừ.
Sự tương đồng giữa số học và bitmask
Bitmask là cách dùng các con số để biểu diễn sự có/không có của phần tử trong tập hợp. Với một bitmask biểu diễn tập hợp, ta có các hàm giá trị , ánh xạ bitmask sang giá trị nguyên.
Trong số học chúng ta có ước chung lớn nhất và bội chung nhỏ nhất ( và ), thì với bitmask, phép AND sẽ tương đồng với , phép OR tương ứng với . Việc áp dụng bao hàm loại trừ khi làm các bài tập về đối với AND, OR tương đồng nhau.
Đối với số học bình thường chúng ta có hàm Mobius để làm các bài toán tổ hợp và bao hàm loại trừ theo ước nguyên tố, thì với bitmask chúng ta cũng có biến đổi Mobius trên hàm .
Biến đổi Zeta và biến đổi Mobius
Trong các tài liệu nước ngoài, DP SOS và SOS ngược còn được gọi với cái tên khác là biến đổi Zeta và biến đổi Mobius. Ta định nghĩa các phép biến đổi như sau:
- Biến đổi Zeta: .
- Biến đổi Mobius:
- Biến đổi đan dấu: .
Phần đan dấu của biến đổi Mobius nhìn như vậy, thật ra là việc ta áp dụng logic của bao hàm loại trừ của lý thuyết tập hợp vào. Ta cộng vào nếu tập con kém tập gốc chẵn phần tử và trừ đi nếu kém lẻ phần tử.
Ta có 1 số định lý sau:
Định lý 1: . Định lý 2: , hay .
Nhờ các công thức gọn gàng ở trên mà các phép biến đổi này đều có thể tính một cách hiệu quả trong với là tổng thời gian cần thiết để gộp kết quả của các tập con.
Đối với phép cộng thông thường, ta duyệt qua tất cả các bit bật của mask và cộng vào, do đó . Tuỳ vào hàm chúng ta định nghĩa phép gộp tập hợp (), mà có thể thay đổi.
Vì có sự tương đồng như đã nói ở trên, nên tư duy tổ hợp của số học và bitmask cũng tương đồng với nhau. Suy cho cùng thì 2 đối tượng toán học này cũng chỉ là 2 cách biểu diễn hình thức của cùng 1 bản chất.
Vận dụng
Chẳng hạn chúng ta có bài toán kinh điển sau:
Cho số . Với mỗi từ 1 đến đếm số tập con có bằng đúng . Giới hạn: .
Gọi là số tập con có bằng đúng . Ta định nghĩa là số tập con có chia hết cho .
Ta có và với là hàm Mobius. Đây là kết quả cơ bản và kinh điển của bao hàm loại trừ.
Dễ thấy với là số phần tử chia hết cho trong dãy, ta có thể tính dễ dàng bằng sàng nguyên tố. Sau đó ta tính được bằng công thức ở trên trong .
Bài toán dưới đây cho thấy sự tương đồng giữa với phép AND.
CF 449D - Jzzhu and Numbers (mở rộng)
Cho số . Với mỗi từ đến đếm số tập con mà AND của các phần tử bằng đúng . Giới hạn: .
Tương tự, gọi là đáp án với cố định, ta định nghĩa là số tập con có AND là một super-mask của (giống với quan hệ chia hết). Khi này ta có và .
Để tập con có AND là super-mask của thì từng số trong dãy phải là super-mask của . Gọi là số lần xuất hiện của , thì chính là số số trong dãy là super-mask của . Như vậy ta có . Qua implementation ở trên ta tính lại được hiệu quả trong .
CF 1620G - Subsequence Galore
Cho tập gồm xâu kí tự . Các kí tự trong tất cả các xâu này đều được sắp xếp. Ta định nghĩa với một tập xâu là số xâu mà là xâu con của ít nhất một xâu trong . Tính với mọi . Giới hạn: .
Với các bài toán ta cần đếm số cấu hình thoả mãn ít nhất một/tất cả/vài điều kiện, điều đầu tiên có thể nghĩ đến là bao hàm loại trừ.
Với mỗi xâu ta có tập xâu con tương ứng của nó. Ta có
Bằng bao hàm loại trừ, ta có thể đưa việc tính tổng hợp về tính tổng giao, và tính tổng giao này thường sẽ có công thức tổng quát. Hay nói cách khác, khi biến đổi SOS xuôi , khó tính được trực tiếp, nhưng thì khả năng cao là tính được, rồi ta SOS ngược để tính .
Từ giả thiết, không khó để ta viết ra được công thức sau:
với là số lần xuất hiện của kí tự trong các xâu thuộc .
Vì mỗi kí tự từ a đến z đóng góp độc lập nhau nên ta có thể tính đóng góp của từng kí tự một rồi nhân các kết quả lại để tối ưu bộ nhớ. (chỉ cần thay vì (với bài này cho ML tận 1024 MB nên vẫn có thể qua, nhưng bình thường sẽ không ngon ăn thế).
Đây cũng là phần ta cần lưu ý. Khi tính theo từng kí tự một, thì khi này operation lấy tổng của chúng ta khi áp dụng SOS là phép lấy min. Với các phép toán idempotent (như min, max, gcd, lcm, AND, OR, etc), ta chỉ cần lấy 1 submask để cập nhật kết quả, chứ không phải duyệt toàn bộ. Với phép lấy min thì ta chỉ cần để cập nhật trạng thái ở mỗi mask. Nên với bước này ta chỉ mất
Có rồi thì ta SOS ngược để tính .
Tổng độ phức tạp cuối cùng là , bộ nhớ là .
Hệ cơ số 2 và hệ cơ số 10
WIP
Che giấu
Đôi khi ý tưởng SOS không dễ nhận ra mà được giấu khá kĩ, điển hình trong bài sau:
ICPC SEERC Regional 2023 bài A - AND-OR Closure
Cho 1 tập gồm số. Ta định nghĩa bao đóng AND-OR của tập là cách thêm ít phần tử nhất vào sao cho: 1. Với thì . 2. Với thì . Tìm kích thước bao đóng AND-OR của . Giới hạn: .
WIP.
Tham khảo
- Author:dnx04
- URL:https://dnx04.vercel.app/article/dp-sos-1-writeup
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
