Glad You Came
시간 제한4초메모리 제한512 MB
0으로 초기화된 배열에 m번의 구간 최댓값 갱신(a_j = max(a_j, v_i))을 적용하되 각 l, r, v는 주어진 32비트 난수 생성기로 만들고, 마지막에 i*a_i의 XOR을 출력한다.
문제
Steve는 길이 (n)인 정수 배열 (a)를 가지고 있다 (1-based). 처음에 모든 원소를 0으로 두었다. 그 후 (m)번의 연산을 수행하는데, 각 연산은 (a)의 한 구간을 어떤 값으로 갱신하는 것이다. 모든 연산이 끝난 뒤 (\oplus_{i=1}^{n}{(i \cdot a_i)})를 구하라. 여기서 (\oplus)는 비트 XOR 연산자이다.
입력 데이터가 커지는 것을 막기 위해, 이 연산들은 특정한 방식으로 암호화되어 있다.
세 개의 부호 없는 32비트 정수 X, Y, Z가 입력으로 주어지며 초깃값을 가진다. 난수 생성 함수는 다음과 같다. 여기서 ∧는 비트 XOR 연산자, <<는 비트 왼쪽 시프트 연산자, >>는 비트 오른쪽 시프트 연산자이다. 이 함수는 호출된 뒤 X, Y, Z의 값을 바꾼다.
1: function RNG61()
2: X ← X ∧ (X << 11) ▷ 32-bit unsigned integer overflow might occur
3: X ← X ∧ (X >> 4)
4: X ← X ∧ (X << 5) ▷ 32-bit unsigned integer overflow might occur
5: X ← X ∧ (X >> 14)
6: W ← X ∧ (Y ∧ Z) ▷ as a partial 32-bit unsigned integer
7: X ← Y
8: Y ← Z
9: Z ← W
10: return Z
11: end function
위 함수를 호출해 얻은 (i)번째 결과값을 (f_i)라 하자 ((i = 1, 2, \dots, 3m)). Steve의 (i)번째 연산은 (a_j < v_i)이면 (a_j)를 (v_i)로 갱신하는 것이다 ((j = l_i, l_i + 1, \dots, r_i)). 여기서
[\begin{cases} l_i = \min {((f_{3i-2} \mod{n}) + 1, (f_{3i-1} \mod{n}) + 1)} \ r_i = \max {((f_{3i-2} \mod{n}) + 1, (f_{3i-1} \mod{n}) + 1)} \ (i = 1, 2, \dots, m)\text{.} \ v_i = f_{3i} \mod{2^{30}} \end{cases}]
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다.
다음 T개의 줄 각각에 하나의 테스트 케이스가 주어지며, 공백으로 구분된 다섯 정수 n, m, X, Y, Z가 있다.
1 ≤ T ≤ 100, 1 ≤ n ≤ 105, 1 ≤ m ≤ 5 · 106, 0 ≤ X, Y, Z < 230.
모든 테스트 케이스에서 n의 합은 106을 넘지 않고, m의 합은 5 · 107을 넘지 않는다.
출력
각 테스트 케이스마다 답을 한 줄에 출력한다.
힌트
첫 번째 예제에서 모든 연산이 끝난 뒤 a = [1031463378]이다.
두 번째 예제에서 모든 연산이 끝난 뒤 a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924]이다.