Editorial for Sơn nhà

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Subtask 1: Ta cần đếm số bộ ba $(i,j,k)$ ~(i,j,k)~ tương ứng với $i$ ~i~ căn nhà màu đỏ, $j$ ~j~ căn nhà màu lam và $k$ ~k~ căn nhà màu lục. Một bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn khi và chỉ khi $A \times i+B \times j+(A+B) \times k = K$ . Khi đó, số cách sơn nhà với bộ ba này là $N \choose i$ ~N \choose i~ $\times$ ~\times~ $N-i \choose j$ ~N-i \choose j~ $\times$ ~\times~ $N-i-j \choose k$ ~N-i-j \choose k~. Lưu ý rằng ta cần sử dụng Nghịch đảo modulo để tính toán.

Độ phức tạp: $O(N^2.\log(N))$ ~O(N^2.\log(N))~

Subtask 2: Ta có thể xem mỗi màu lục được tạo thành từ hai màu đỏ và lam. Ta chỉ cần đếm số cặp $(i,j)$ ~(i,j)~ tương ứng với $i$ ~i~ căn nhà màu đỏ và $j$ ~j~ căn nhà màu xanh, nhưng mỗi căn nhà có thể được tô cả hai màu. Một cặp $(i,j)$ ~(i,j)~ thỏa mãn khi và chỉ khi $A \times i + B \times j = K$ ~A \times i + B \times j = K~. Khi đó, số cách sơn nhà với cặp $(i,j)$ ~(i,j)~ này là $N \choose i$ ~N \choose i~ $\times$ ~\times~ $N \choose j$ ~N \choose j~.

Độ phức tạp: $O(N.\log(N))$ ~O(N.\log(N))~

Editorial for Sơn nhà

Comments