https://www.acmicpc.net/category/detail/3593

== 미리보기 스포일러 방지 ==

== 미리보기 스포일러 방지 ==

N-R을 m으로 나눈 나머지가 0이어야 합니다. 즉, m은 N-R의 약수여야 합니다.

그렇다고 다 되는 건 아니고, m이 R보다 커야 합니다. 즉, N-R의 약수 중 R보다 큰 것의 개수를 세면 됩니다.

어떤 수 X의 약수는 O(sqrt(X)) 시간에 전부 알아낼 수 있음이 알려져 있습니다. https://www.acmicpc.net/step/18

모든 이동 거리의 합을 구해서 N!로 나눈다고 생각해 봅시다. (그렇다고 진짜로 합을 구해서 N!로 나누면 안 됩니다. 너무 크기 때문에...)

어떤 사람 쌍 a->b에 대해, 가능한 N!개의 경로 중 a->b가 포함된 경로가 몇 개인지 구해봅시다. 그 값에다가 a와 b 사이 거리를 곱하고, 모든 쌍에 대해 그걸 다 더하면 됩니다.

경로에는 길이 정확히 N-1개 있습니다. 그중 a->b가 i번째 길이라고 하면, 나머지를 채우는 경우의 수는 (N-2)!입니다. 모든 i에 대해 이 값이 동일하기 때문에 전체 경우의 수는 여기에 N-1을 곱한 (N-1)!입니다. b->a도 고려하면 2(N-1)!입니다.

따라서 문제의 답은 (모든 쌍의 거리의 합) * 2(N-1)! / N!이고, 이를 정리하면 (모든 쌍의 거리의 합) * 2 / N입니다. 이렇게 하면 N! 같은 너무 큰 수를 쓰지 않고 답을 구할 수 있습니다.

• a는 l 이상의 수 중 S[a] = R인 가장 작은 수,
• b는 a+1 이상의 수 중 S[b] = R인 가장 작은 수,
• d는 r 이하의 수 중 S[d] = B인 가장 큰 수,
• c는 d-1 이하의 수 중 S[d] = B인 가장 큰 수

라고 합시다. 만약 a, b, c, d 중 하나라도 존재하지 않거나, c > b이면 답은 -1이고, 아니면 찾은 a b c d를 그대로 출력하면 됩니다.

a와 b를 찾으려면 S[i] = R인 i들을 차례대로 저장해 놓은 배열을 따로 만들고, 거기서 이분 탐색을 돌리면 됩니다. c와 d도 마찬가지입니다.

k에 대한 조건이 없으면 왜 문제가 너무 쉬워질까요? 그냥 모든 x에 대해 k = 1 질문을 한 번씩 해 주면 되기 때문입니다. 하지만 k의 값이 모두 달라야 하기 때문에 그럴 수는 없습니다.

순열을 가지고 그래프를 만들면 여러 개의 사이클이 나온다는 사실이 알려져 있습니다. 이 사이클들을 찾으면 됩니다.

우선 x = 1부터 봅시다. k = 1 질문을 하면 A[x]를 알 수 있습니다. 그 다음에 A[x]에서 k = 1 질문을 하면 A[A[x]]를 알 수 있습니다. 그 다음에 A[A[x]]에서 k = 1 질문을 하면 ... 이런 식으로 반복하다가 1로 돌아오면 1이 들어있는 사이클을 찾을 수 있습니다. 물론 이 방법도 k = 1 질문을 여러 번 하고 있으니까 쓸 수 없습니다.

다행히도, A[x]에서 k = 1 질문을 하는 것은 1에서 k = 2 질문을 하는 것으로 대체할 수 있습니다. A[A[x]]는 1에서 k = 3 질문을 하면 되고요. 그래서 1에서 k = 1부터 하나씩 늘려가며 질문을 하다가 답으로 1이 나오면, 그때 k의 값이 사이클의 길이일 것입니다. 이 방식으로 1이 들어있는 사이클을 찾을 수 있습니다.

그럼 다른 사이클은??

어떤 x가 들어있는 사이클을 아직 못 찾았다고 합시다. 더 이상 k = 1 질문을 할 수 없고, 그 대신 지금까지 질문했던 모든 k보다 큰 값 K를 잡아 질문해 봅시다. 그럼 어떤 y가 답으로 나올 것이고, 이제 y에서 특정 k로 질문을 하는 것은 x에서 k+K 질문을 하는 것으로 대체할 수 있습니다. 그래서 k = K+1부터 하나씩 늘려가며 질문을 하면 됩니다.

위 방법을 사용하면 사이클의 길이가 C일 때 C+1개의 질문으로 그 사이클을 찾을 수 있습니다. 이때 질문의 효율은 (C+1)/C입니다. 즉 각 원소마다 평균 (C+1)/C번의 질문이 필요한 셈입니다. C = 2일 때 이 값은 3/2니까, 문제에서 원하는 3N/2 조건에 딱 들어맞습니다.

근데 C = 1이면???

어떤 x가 들어있는 사이클의 길이가 1이라면 그 사실을 질문 단 하나로 알 수 있어야 합니다. 일단 사이클 길이가 1이면 답으로 무조건 x만 나올 것이고, 사이클 길이가 2 이상이면 x가 안 나오도록 하는 것이 목표입니다. 그러려면 최초의 질문 K를 잡을 때, K가 1을 제외한 어떤 사이클 길이의 배수도 아니어야 합니다.

그런데 "1을 제외한 누구의 배수도 아님", 이거 소수의 정의에서 본 것 같습니다. N이 최대 1,000이니까 사이클 길이도 최대 1,000입니다. 따라서 K가 1,000 이상의 소수면 됩니다.

보너스 문제: 질문을 N번만 해서 풀어 보세요.