Editorial for Bedan Contest #05 - G - Xếp xe


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.

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.


Comments

There are no comments at the moment.