NKPATROL - Robot tuần tra
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một cái sân hình vuông có cạnh N (đơn vị độ dài). Các hàng (cột) của sân được đánh số từ 1-->N. Sân được chia thành N^2 ô vuông đơn vị. Ô tại hàng i cột j có tên là (i,j). Trên sân chỉ cho phép đi ngang hoặc dọc (nhưng có thể di chuyển nhiều ô 1 lúc). Vào buổi tối, người ta dùng một con Robot để canh gác.
Ban đầu Robot được đặt tại một ô bất kì. Sau đó Robot sẽ tự chọn ra một đường đi trên sân và sẽ lặp lại đường đi đó cho đến sáng. Vì thế, Robot đã được lặp trình thỏa một số điều kiện:
- Để cho việc lặp lại đường đi, điểm đầu phải trùng với điểm cuối.
- Để đảm bảo an toàn, Robot phải đi trên tất cả các hàng và các cột.
- Để tiết kiệm, Robot không được đi quá một lần trên một hàng hoặc một cột.
Ta nói Robot đi trên một hàng (hoặc cột ) là khi Robot đi giữa hai ô nằm trên cùng một hàng (hoặc cột ). Có thể trong lúc đi chuyển Robot sẽ cắt với một hàng (hoặc cột) tại đúng một ô nào đó, nhưng ta không gọi đó là đi trên hàng (hoặc cột).
Ví dụ: N=4, di chuyển ngang từ ô (2,1) đến (2,4) thì:
+ Robot đi trên hàng số 2.
+ Đường đi có cắt cột số 3 tại ô (2,3), nhưng đây không được gọi là đi trên cột số 3.
Yêu cầu: Đếm số dạng đường đi có thể. Biết hai dạng đường đi gọi là khác nhau nếu hình vẽ của chúng trên sân là khác nhau.
Giới hạn:
_ N<=1000000000
_ 40% test có N<=1000
_ 80% test có N<=1000000
Input
_ Dòng duy nhất là số N - kích thước của sân.
Output
_ Cho biết số dạng đường đi có thể trên sân. Do kết quả có thể rất lớn, hãy in phần dư khi chia kết quả cho 939999953.
Example
Input: 3 Output: 6
Giải thích: có 6 cách đi
1. (1,1) --> (1,3) --> (2,3) --> (2,2) --> (3,2) --> (3,1) --> (1,1)
2. (1,1) --> (1,3) --> (3,3) --> (3,2) --> (2,2) --> (2,1) --> (1,1)
3. (1,1) --> (1,2) --> (2,2) --> (2,3) --> (3,3) --> (3,1) --> (1,1)
4. (1,2) --> (1,3) --> (3,3) --> (3,1) --> (2,1) --> (2,2) --> (1,2)
5. (1,1) --> (1,2) --> (3,2) --> (3,3) --> (2,3) --> (2,1) --> (1,1)
6. (1,2) --> (1,3) --> (2,3) --> (2,1) --> (3,1) --> (3,2) --> (1,2)
Ta có (3,3) --> (1,3) --> (1,2) --> (2,2) --> (2,1) --> (3,1) --> (3,3)
cũng là một đường đi đúng, nhưng hình vẽ của nó đã trùng với hình của đường số 4.
Sân N=3 và 6 dạng đường đi (xem mỗi ô trên sân là 1 chấm đỏ) .
- Người up: yellowflash12
- Nguồn bài: Trần Anh Hướng Thái Huy