시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 300 | 59 | 49 | 31.410% |
지승이는 대학교에서 수학을 가르치고 있다. 이번학기에는 "이산 수학과 조합론"을 가르치며, 수강생은 총 N명이다. 지난 시간에 강의한 내용은 순열의 순서(Ranks of permutations)이다.
1부터 K까지 이루어진 수열이 있을 때, 각 숫자가 한 번씩만 등장하는 수열을 순열이라고 한다. 순열은 총 K!가지 경우의 수가 있을 수 있다. 수열 (1, 2, 3)은 총 3! = 6가지 방법으로 나타낼 수 있다. 순열은 첫 번째 숫자를 비교하고, 두 번째 숫자를 비교하고, ..., 이와 같은 방식으로 계속해서 비교하는 방식으로 순서를 매길 수 있다.
한 수열로 만들 수 있는 순열을 모두 순서대로 나열했을 때, 인덱스가 순열의 순서된다. 예를 들어, (3, 1, 2)의 순서는 5가 된다.
지승이는 학생들에게 순열의 순서를 계산하는 숙제를 내주려고 한다. 한 학생에게 순열을 하나 알려주고, 그 학생은 다음 수업 전까지 그 순열의 순서를 구해와야 한다.
지승이는 간단한 알고리즘을 이용해 숙제에 낼 순열을 만들려고 한다.
먼저, K개의 숫자로 이루어진 순열을 하나 아무거나 고른다. 그 다음, 학생마다 A와 B를 골라 A번째 수와 B번째 수의 위치를 바꾼 순열을 새롭게 만든다.
예를 들어, 고른 순열이 (1, 5, 4, 2, 3)이고, 고른 A와 B가 (1, 3), (2, 3), (2, 5)라면, 학생들이 받게되는 순열은 (4, 5, 1, 2, 3), (1, 4, 5, 2, 3), (1, 3, 4, 2, 5)가 된다. 각 순열의 순서는 91, 17, 9이다.
지승이가 고른 순열과 A와 B가 주어졌을 때, 각 순열의 순서를 구하는 프로그램을 작성하시오. 순서가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다.
첫째 줄에 K와 N이 주어진다. (2 ≤ K ≤ 300,000, 1 ≤ N ≤ 100,000) K는 순열의 길이, N은 학생의 수이다.
둘째 줄에는 지승이가 고른 순열이 주어진다. 순열은 1부터 K까지 정수 K개로 이루어져 있으며, 한 숫자는 한 번만 등장한다.
다음 N개 줄에는 A와 B가 주어진다. (1 ≤ A < B ≤ K)
한 줄에 하나씩 순열의 순서를 1,000,000,007로 나눈 나머지를 출력한다.
5 3 1 5 4 2 3 1 3 2 3 2 5
91 17 9
15 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 15 1 15
2 246045325
Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Final Exam #1 1번