Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PERC - Chu trình hoán vị

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/perc


                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 (a1, a2, a3, … , an) và (b1, b2, b3, … ,bn) được định nghĩa như sau
            (a1, a2, a3, … , an) x (b1, b2, b3, … ,bn) = (ab1,ab2, ab3, …, abn)
            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ị :
            (a1, a2, a3, … , an)2 = (a1, a2, a3, … , an) x (a1, a2, a3, … , an)
            (a1, a2, a3, … , an)k = (a1, a2, a3, … , an) x (a1, a2, a3, … , an) x … x (a1, a2, a3, … , an)  (k phép nhân hoán vị) 

            Nam nhận thấy có những số nguyên X mà (a1, a2, a3, … , an)X = (a1, a2, a3, … , an). Khi đó ta gọi X là một chu trình của (a1, a2, a3, … , an).
            Với một một hoán vị ban đầu (a1, a2, a3, … , an). 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 (a1, a2, a3, … , an). Hãy giúp Nam.

Input

            Dòng đầu ghi số nguyên dương N (1 <= N <= 2x106)
            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 109+7.       
            Dữ liệu vào bảo đảm có kết quả.
            Trong 30% số test có N <= 500,  K <= 5x105
            Trong 50% số test, K <= 1018

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

Được gửi lên bởi:Alex & Friends
Ngày:2012-12-30
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:by winterwolf94

hide comments
2016-08-17 12:36:06 noname00.pas
Lý thuyết cho bài này: http://dis.unal.edu.co/~gjhernandezp/sim/lectures/permutations/1003permutations.pdf
2014-10-21 16:36:33 Anh Vu
lINK TRÊN KIA NOT FOUND ROI.
2013-07-25 10:26:19 Hồ Hữu Sơn
Chu kì k của hoán vị bằng bội chung nhỏ nhất của các chu kì của từng số
2013-02-21 05:31:40 Danh Nguyen
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDUQFjAA&url=http%3A%2F%2Fwww-groups.mcs.st-andrews.ac.uk%2F~martyn%2Fteaching%2F1003%2F1003permutations.pdf&ei=_rAlUeWzMqfA2gWH1oHIDQ&usg=AFQjCNE38JZf0fbbaLeViIv_o8Vlugae_g&sig2=EX5iY8fkDqh9JP-5SHQY1g
2012-12-31 01:24:55 MD
ps xem hộ e bị TLE hay WA với ạ!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.