시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 16 MB 121 48 17 34.694%

문제

0 부터 N - 1 까지 번호가 부여된 N 개의 정점을 가진 완전그래프가 있다.

각 정점 i 는 어떤 값 Xi 를 가지고 있다.

번호의 크기 관계가 i  < j  를 만족하는 두 정점 ij 사이를 연결하는 양방향 간선의 가중치 dist(i, j) 는 다음과 같이 계산된다.

dist(i, j) = ((Xi  × A + Xj  × B) % C) ^ D

여기서 ABCD 는 상수이고, % 는 나눗셈의 나머지 연산, ^ 는 bitwise XOR 연산을 의미한다.

주어진 그래프의 최소 신장 트리 (MST) 의 가중치를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N 이 주어진다.

두 번째 줄에는 4 개의 정수 A, B, C, D 가 차례대로 주어진다.

세 번째 줄에는 N 개의 정수가 주어진다. 이는 Xi 가 0 번 정점부터 시작해서 N-1 번까지 순서대로 주어진 것이다.

입력으로 주어지는 모든 수는 제약사항의 범위를 만족하는 정수이며, 각 수는 공백으로 구분된다.

출력

최소 신장 트리의 가중치를 출력한다.

제한

  • 1 ≤ N ≤ 10,000
  • 0 ≤ Xi, A, B, C, D ≤ 1,000,000,000,000
  • C ≠ 0

예제 입력 1

5
76 98 73 42
3 2 13 16 7

예제 출력 1

18

예제 입력 2

7
687616258876 548342706698 598924357642 479342226273
474585935261 621191507020 781184643570 736346504107 987108549969 385099936705 997944222071

예제 출력 2

779662173222

노트

시간 / 메모리 제한으로 인해 C/C++ 와 Java11, 그리고 PyPy3 이외의 언어로는 정해로도 정답을 받을 수 있는 것이 보장되지 않는다.

출처

채점 및 기타 정보

  • 이 문제의 채점 우선 순위는 2이다.