페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3618

수열 정렬 5s 4MB

문제

아래 점화식으로 만들어지는 길이 N의 수열이 주어지면 배열을 오름차순으로 정렬했을 때 K번째 수를 구하는 프로그램을 작성하여라.

  • A_1 = a

  • A_2 = b

  • A_i = ((A_{i-1}+A_{i-2}) \ XOR \ i) \ mod \ 2^{30} \ (i ≥ 3)

N개의 수를 배열에 저장하기에는 메모리가 부족함에 유의하여라.​ 


입력

첫째 줄에 N, a, b, Q가 주어진다. (3 ≤ N ≤ 2,000,000, 0 ≤ a, b < 230, 1 ≤ Q ≤ 1,000)

둘째 줄에 Q개의 K가 주어진다. (1 ≤ K ≤ N)

 


출력

Q개의 K에 대하여 K번째 수를 공백을 사이에 두고 출력한다. 


예제 #1

10 3 6 10

1 2 3 4 5 6 7 8 9 10
3 6 10 20 27 41 67 100 174 280

예제 #2

2000000 581293719 846193005 7

2 20 200 2000 20000 200000 2000000
652 15066 128415 1109991 10728565 107400605 1073741029

로그인해야 코드를 작성할 수 있어요.