**PHÁT BIỂU LẠI BÀI TOÁN**
"Có $n - 1$ cây nấm, cây nấm thứ $i$ mang màu sắc $i + 1$." $\implies$ Cho tập số nguyên dương $N = \\{ 2; 3; 4; \dots; n\\}$.
"Marisa và Reimu mỗi người sẽ hái một số cây nấm và bỏ vào giỏ của họ (Có thể không hái cái nào)." $\implies$ Chọn hai tập con rời nhau $M$ và $R$ của $N$.
Điều kiện để hai giỏ nấm hoàn hảo tương đương với việc không tồn tại hai số nguyên dương $m \in M$ và $r \in R$ sao cho $UCLN(m, r) > 1$, tức là mọi cặp số nguyên dương $(m, r)$ đều không có chung ước số nguyên tố nào.
**HƯỚNG ĐI**
Dễ thấy để hai tập con $M$ và $R$ hoàn hảo thì mọi thừa số nguyên tố $p$ từ các số đã chọn chỉ nằm trong một trong hai tập trên.
Có thể sử dụng hai trạng thái bitmask $i$ và $j$ để thể hiện sự xuất hiện của các thừa số nguyên tố trong mỗi tập con, với điều kiện hoàn hảo tương đương $i \\& j = 0$.
Tuy nhiên, nếu trực tiếp bitmask như vậy thì mỗi mask sẽ dài $\pi(n) \le 95$ với $n \le 500$, chắc chắn không đủ nhanh khi có ít nhất $(2^{95})^2$ cặp $(i, j)$ khác nhau.
Do đó, ta cần tìm cách giảm bớt độ dài của mỗi mask qua việc xử lí riêng một số thừa số nguyên tố đặc biệt nào đó.
**Ý TƯỞNG 1**
Tạm thời bỏ qua hai tập con $M$ và $R$, ta thấy mọi số nguyên tố $p$ trong tập $N$ có thể xuất hiện lại trong các bội từ $2p$ của nó: $2p; 3p; 4p; \dots; \lfloor \frac{n}{p} \rfloor p$
Khi $2p > n$ hay $p > \lceil \frac{n}{2} \rceil$ thì số nguyên tố $p$ chỉ xuất hiện đúng một lần trong tập $N$ và có thể tách ra để xử lí riêng.
Lúc này, mỗi mask còn dài $\pi(\lceil \frac{n}{2} \rceil) \le 53$ với $\lceil \frac{n}{2} \rceil \le 250$, khá hơn trước, nhưng vẫn chưa đủ nhanh.
Ta cần siết chặt các số nguyên tố đặc biệt này hơn là chỉ từ $\lceil \frac{n}{2} \rceil$ trở lên. Trước khi đọc ý tưởng 2, bạn đọc có thể xem lại thuật toán [sàng nguyên tố Eratosthenes](https://wiki.vnoi.info/algo/algebra/prime_sieve.md) để nghĩ được cách siết chặt hơn.
**Ý TƯỞNG 2**
Thay vì chỉ siết các số nguyên tố xuất hiện đúng một lần trong $N$, ta có thể "mạnh tay" với cả những số xuất hiện đúng một lần trong mỗi phần tử thuộc $N$(!)
Các số nguyên tố $p$ thỏa mãn điều trên tương đương với $p^2 > n$ hay $p > \sqrt n$, tạm gọi là các thừa số nguyên tố "lớn". Các bội của các số nguyên tố này có thể phân tích thành thừa số nguyên tố "lớn" đó và các thừa số nguyên tố "nhỏ" còn lại.
(Cũng giống với việc khi gặp một số nguyên tố $p$ trong sàng nguyên tố, thay vì sàng từ $2p$, ta có thể sàng từ $p^2$ vì các bội của $p$ bé hơn $p^2$ đã được sàng, hay quản lí trước, bởi các số nguyên tố nhỏ hơn $p$).
Với cách làm này thì mỗi mask chỉ còn dài $\pi(\sqrt n) \le 8$ với $\sqrt n \le 23$, hoàn toàn đủ nhỏ để quản lí.
**THỰC THI**
Ta định nghĩa $dp\[i\]\[j\]$ là số cách chọn hai tập con $M$ và $R$ hoàn hảo sao cho các thừa số nguyên tố "nhỏ" trong $M$ và $R$ lần lượt thể hiện qua hai bitmask $i$ và $j$, mỗi mask có 8 vị trí bit lần lượt thể hiện các số nguyên tố $2; 3; 5; 7; 11; 13; 17; 19$.
Trường hợp cơ sở: $dp\[0\]\[0\] = 1$ với cách chọn $M = R = \\{\\}$
Liên hệ giữa các trạng thái: Ta lần lượt mở rộng "vùng chọn" trong $N$ bằng cách lần lượt thêm các số $2; 3; 4; \dots; n$ vào để xử lí:
> Nếu số được thêm vào chỉ có các thừa số nguyên tố "nhỏ", bản thân số đó cũng có thể mask thành một bitmask $k$ có 8 vị trí bit tương tự như $i$ và $j$. Ở trạng thái $\[i\]\[j\]$, nếu $k \\& j = 0$ thì với mỗi cách chọn tập con hoàn hảo, số này cũng có thể tiếp tục cho vào tập $M$ tạo thành bitmask $i | k$ đảm bảo $(i | k) \\& j = 0$.
> Tóm lại, nếu $k \\& j = 0$ thì $dp\[i|k\]\[j\] \leftarrow dp\[i|k\]\[j\] + dp\[i\]\[j\]$ và tương tự với $k \\& i = 0$.
> Nếu số được thêm vào là một số nguyên tố "lớn" $p$, ta lập tức xử lí $p$ cùng các bội đến $\lfloor \frac{n}{p} \rfloor p$ (sau đó, khi gặp lại một bội của $p$, ta bỏ qua không xử lí nữa). Nếu bỏ đi thừa số $p$ thì mỗi số còn lại trong tập bội trên của $p$ cũng lại có thể phân tích các thừa số nguyên tố "nhỏ" còn lại thành một bitmask $k$ cùng loại như trên. Tuy nhiên, ta không chỉ xét riêng lẻ từng bội mà còn phải xét qua mọi tập con của tập bội này để biết được có bao nhiêu tập con tạo được mỗi mask $k$ (bằng cách làm thêm một bước DP nhỏ, gợi ý: [DP Knapsack](https://wiki.vnoi.info/algo/dp/dp-knapsack-1)).
> Giả sử có $x$ tập con của tập bội đó tạo được bitmask $k$ sao cho $k \\& j = 0$ tương tự như trên. Với mỗi cách chọn tập $M$ và $R$ hoàn hảo ở trạng thái $\[i\]\[j\]$, ta có $x$ cách chọn một tập con của tập bội để cho vào $M$ mà vẫn hoàn hảo. Do đó, phép gán sẽ là $dp\[i|k\]\[j\] \leftarrow dp\[i|k\]\[j\] + x \cdot dp\[i\]\[j\]$, với mọi mask $k$ có thể tạo được và tương tự cho $k \\& i = 0$.
Kết quả cuối cùng: Tổng của mọi $dp\[i\]\[j\]$ thỏa $i \\& j = 0$ (về lí thuyết thì $dp\[i\]\[j\] = 0$ với $i \\& j > 0$ nên cũng có thể không cần trực tiếp kiểm tra điều kiện hoàn hảo).
Một số lưu ý:
> Thứ tự cập nhật $dp$ khi thêm số nguyên tố "lớn" có thể hỗn loạn và ghi đè lên các giá trị sai, do đó cần lưu riêng $dp$ cũ và $dp$ mới.
> Lưu ý $mod$ của đề bài khi thực hiện các phép tính.
sasaki2c
Created at
3 likes