Hướng dẫn cho Bedan Contest #05 - G - Xếp xe

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Cách giải

Hint

Khi đặt quân xe thứ $1$ trên bàn cờ, ta dễ dàng thấy nó sẽ phong tỏa $1$ cột và $1$ hàng mà giao điểm của cột và hàng đó là vị trí của quân xe trên bàn cờ. Tiếp tục đặt quân xe thứ $2$ trên bàn cờ, ta dễ dàng thấy nó sẽ tiếp tục phong tỏa $1$ cột và $1$ hàng nữa. Và sau khi đặt $2$ quân cờ trên, ta dễ dàng thấy có $2$ cột và $2$ hàng phân biệt đã bị phong tỏa.

Solution

Từ nhận xét trên, ta dễ dàng thấy khi đặt $i$ quân xe lên bàn cờ thì sẽ còn $n-i$ vị trí để đặt $n-i$ quân xe còn lại lên bàn cờ. Khi đó, đáp án của chúng ta sẽ là $n \times (n-1) \times (n-2)$ $\times$ $...$ $\times$ $2 \times 1$ hay là $n!$ .
Để tính $n!$ $mod$ $p$ với $p = 1234567891$ ở bài này, ta sẽ loại tất cả các số $n$ lớn hơn $p-1$ . Và với các số còn lại, ta sẽ sử dụng chia căn để tính trước kết quả và tính $n!$ cho mỗi test trong $O(\sqrt{p})$ . Tuy nhiên code của bạn nộp lên TLE-oj chỉ được chứa tối đa là $2^{16}-1$ kí tự nên thay vì tính trước $\sqrt{p}$ số cách nhau $\sqrt{p}$ đơn vị, bạn có thể tính trước $p^{\frac{1}{3}}$ số cách nhau $p^{\frac{2}{3}}$ đơn vị. Đề làm điều này thì đơn giản là bạn tính trước bên ngoài rồi bỏ tất cả vào một mảng trong code.
Độ phức tạp của ý tưởng trên là $O(t \times p^{\frac{2}{3}})$ với $p = 1234567891$ .

Bình luận

Không có bình luận nào.