쉽게 제한된 메모리
시간 제한7초메모리 제한4 MB
의사난수로 생성된 수열 전체를 저장하지 않고 각 질의의 q번째 작은 값을 구해 합을 출력한다.
문제
정수 N개로 이루어진 배열 X가 있다. 쿼리가 몇 개 주어지고, 각 쿼리는 정수 q 하나로 표현된다. 각 쿼리마다 배열 X에서 q번째로 작은 원소를 구해야 한다. q는 0부터 시작하는 인덱스다. 즉 q = 0이면 가장 작은 원소, q = 1이면 두 번째로 작은 원소다.
정렬한 뒤 답을 출력하면 끝나는 쉬운 문제로 보인다. 그래서 이 문제는 메모리 제한을 아주 작게 잡아 그 방법을 막는다. 배열 X 전체를 저장할 수 없다. 대신 쿼리 개수는 적어서 쿼리 정보는 모두 저장할 수 있다.
배열 X는 직접 주어지지 않고, N, x0, a, b로부터 다음 의사코드처럼 생성된다.
X[0] = x0
for i = 1 to N-1:
X[i] = (X[i-1] * a + b) % 1000000007
곱셈에서 오버플로가 일어나지 않도록 주의한다.
모든 쿼리의 답을 더한 값을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 정수 N, x0, a, b가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ x0, a, b ≤ 1,000,000,006)
둘째 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 100)
셋째 줄에 쿼리를 나타내는 정수 Q개가 공백으로 구분되어 주어진다. (0 ≤ q ≤ N-1)
출력
모든 쿼리의 답을 더한 정수 하나를 출력한다.