RABGAME - Trò chơi thỏ
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 7000 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.
Ta xét 1 trò chơi như sau
N con thỏ lần lượt đứng ở các vị trí 1 , 2 , ... , n - 1 , n. Cho 1 hoán vị A gồm N số. Sau 1 đơn vị thời gian, tất cả các con thỏ sẽ đồng loạt nhảy. Con thỏ ở vị trí i sẽ nhảy đến vị trí A[i]. Dễ nhận thấy sau 1 khoảng thời gian nào đó sau khi bắt đầu trò chơi, các con thỏ sẽ trở về vị trí ban đầu.
Trò chơi này xưa như Alibaba nên Duy đã nghĩ ra 1 vấn đề khác hay hơn rất nhiều :D đếm số lượng hoán vị A thỏa mãn sau đúng 2 đơn vị thời gian thì tất cả các con thỏ trở về vị trí ban đầu.
Tuy nhiên, Duy nghĩ mãi mà không nghĩ ra. Các bạn hãy giúp Duy nhé :D
Input
1 số n duy nhất( n <= 500 )
Output
Kết quả của bài toán
Example
Input
2
Output
2
P/s: có vài bạn thấy đề khó hiểu, mình xin giải thích kĩ
Xét n = 2 và hoán vị A là 2 1
Ban đầu con thỏ 1 ở vị trí 1, con thỏ 2 ở vị trí 2
Sau 1 đv, con thỏ 1 sang vị trí A[1] là vị trí 2
Con thỏ 2 sang vị trí A[2] là vị trí 1
Sau 1 đv nữa, con thỏ 1 đang ở vị trí 2 đến vị trí A[2] là 1
Con thỏ 1 ở vị trí 1 đến vị trí A[1] là 2
=> trở về vị trí ban đầu
Quên chưa nói 1 điều, dạo này mình lười nên sinh test random, các bạn chạy trâu ko ăn được điểm đâu :p
- Người up: franco1
- Nguồn bài: Lấy ý tưởng từ 2 bài, 1 của thầy Hoàng và 1 của cô Chinh( HNUE )