Số vòng hoán vị

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng đã sắp xếp $[1, 2, \dots, n]$ và hoán vị $p_{1}, p_{2}, \dots, p_{n}$ . Mỗi vòng, tất cả các phần tử dịch chuyển theo hoán vị: phần tử ở vị trí $i$ chuyển sang vị trí $p_{i}$ .

Hỏi sau bao nhiêu vòng thì mảng trở về trạng thái ban đầu lần đầu tiên?

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .

Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ .

Dữ liệu ra

In số vòng cần thiết modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
8 5 3 2 6 4 1 8 7	4	Sau 4 vòng mảng trở về $[1, 2, 3, 4, 5, 6, 7, 8]$ .
1 1	1	Hoán vị đồng nhất luôn trở về sau 1 vòng.

Bình luận

Không có bình luận tại thời điểm này.