Trò Chơi Hoán Vị Vòng

Algorithms Buổi 10 — STL Algorithms Implementation
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho một hoán vị $P$ của $N$ phần tử (từ 1 đến $N$). Bạn được phép thực hiện thao tác "next permutation" nhiều lần. Bạn cần tìm số bước ít nhất để biến $P$ thành hoán vị $Q$ cho trước. Nếu $Q$ đứng trước $P$ theo thứ tự từ điển, thì bạn cần đi qua hoán vị cuối ($N, N-1, \ldots, 1$) rồi quay lại hoán vị đầu ($1, 2, \ldots, N$) và tiếp tục.

Vì kết quả có thể rất lớn, in ra số bước modulo $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa hoán vị $P$.
  • Dòng thứ ba chứa hoán vị $Q$.
Dữ liệu ra
  • In ra số bước modulo $10^9 + 7$.
Ví dụ
Input Output
3
1 2 3
2 1 3
2
3
2 1 3
1 3 2
5
Giới hạn
  • $1 \le N \le 12$
Draft saved