PERC - Chu trình hoán vị
Giới hạn- Thời gian: 1.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.
Nam rất thích hoán vị. Một hoán vị N là một cách sắp xếp N số nguyên dương từ 1 đến N, mỗi số chỉ xuất hiện một lần. Ví dụ 1 3 5 2 4 là một hoán vị 5.
Phép nhân 2 hoán vị N (a 1 , a 2 , a 3 , … , a n ) và (b 1 , b 2 , b 3 , … ,b n ) được định nghĩa như sau
(a 1 , a 2 , a 3 , … , a n ) x (b 1 , b 2 , b 3 , … ,b n ) = (a b1 ,a b2 , a b3 , …, a bn )
Ví dụ : (2 5 1 4 3) x (3 4 2 5 1) = (1 4 5 3 2)
Phép lũy thừa hoán vị được định nghĩa theo phép nhân hoán vị :
(a 1 , a 2 , a 3 , … , a n ) 2 = (a 1 , a 2 , a 3 , … , a n ) x (a 1 , a 2 , a 3 , … , a n )
(a 1 , a 2 , a 3 , … , a n ) k = (a 1 , a 2 , a 3 , … , a n ) x (a 1 , a 2 , a 3 , … , a n ) x … x (a 1 , a 2 , a 3 , … , a n ) (k phép nhân hoán vị)
Nam nhận thấy có những số nguyên X mà (a 1 , a 2 , a 3 , … , a n ) X = (a 1 , a 2 , a 3 , … , a n ). Khi đó ta gọi X là một chu trình của (a 1 , a 2 , a 3 , … , a n ).
Với một một hoán vị ban đầu (a 1 , a 2 , a 3 , … , a n ). Nam muốn tìm số nguyên dương K nhỏ nhất sao cho K+1 là một chu trình của (a 1 , a 2 , a 3 , … , a n ). Hãy giúp Nam.
Input
Dòng đầu ghi số nguyên dương N (1 <= N <= 2x10 6 )
Dòng thứ 2 gồm N số nguyên dương khác nhau đôi một thể hiện hoán vị ban đầu.
Output
Gồm một số nguyên M duy nhất là số dư của K cho 10 9 +7.
Dữ liệu vào bảo đảm có kết quả.
Trong 30% số test có N <= 500, K <= 5x10 5
Trong 50% số test, K <= 10 18
Example
Input: 5 5 3 2 1 4
Output: 6
Input: 5 1 2 3 4 5
Output: 1
Input: 5 5 4 3 2 1
Output: 2
- Người up: yellowflash12
- Nguồn bài: by winterwolf94