trang chủ / đề bài / colorbricks / lời giải

Gạch màu

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Lời giải: Gạch màu

Hướng tiếp cận

Sử dụng tổ hợp để đếm số cách chọn vị trí và màu.

Nhận xét quan trọng

Cần chọn đúng $k$ vị trí trong $n - 1$ vị trí (vị trí 2 đến n) để có màu khác bên trái.
Viên gạch đầu tiên có $m$ cách chọn màu.
Mỗi vị trí "khác màu" có $m - 1$ cách chọn (khác màu bên trái).
Các vị trí "cùng màu" chỉ có 1 cách (giống màu bên trái).

Thuật toán

Áp dụng quy tắc nhân:

Chọn $k$ vị trí trong $n - 1$ vị trí: $C (n - 1, k)$ cách
Viên đầu tiên: $m$ cách
$k$ vị trí khác màu: mỗi vị trí có $m - 1$ cách

Công thức: $C (n - 1, k) \times m \times (m - 1)^{k} \mod 998244353$

Độ phức tạp

Thời gian: $O (n)$ tiền xử lý giai thừa, $O (\log k)$ tính lũy thừa
Bộ nhớ: $O (n)$

Bình luận

Không có bình luận tại thời điểm này.