20390번 - 완전그래프의 최소 스패닝 트리 분류

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

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

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

dist(i, j) = ((X_i  × A + X_j  × B) % C) ^ D

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

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

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

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

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

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

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

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

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