시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 187 25 23 22.549%

문제

경근이는 세계에서 제일가는 콩나무 농부가 꿈이다. 오늘도 꿈을 이루기 위해서 고군분투 하던 경근이는 마침내 식물에게 뿌리기만 하면 식물이 쑥쑥 자라게 하는 비료X를 개발하는데 성공했다. 다만 비료X의 너무나도 강력한 효과를 잘 제어할 자신이 없었던 경근이는 비료X의 강도를 서서히 높여가면서 콩나무 기르기에 익숙해지고자 마음먹었다.

경근이는 현재 N개의 콩나무 씨앗을 가지고 있으며, 이제 막 씨앗들을 땅에 심었기 때문에 높이가 0이다. 경근이는 앞으로 D일에 걸쳐 하루에 한 번씩 콩나무들에게 비료를 주고자 한다.

i (1 ≤ i ≤ D)번째 날에는 비료를 흡수하면 높이가 i만큼 자라도록 비료X를 주려고 하는데, 이 때 비료를 주는 대상은 현재 높이가 가장 낮은 Ci개의 나무이다.

또한 경근이는 비료가 콩나무들이 얼마나 잘 자라는지 알고 싶기 때문에 매일매일 비료를 주고 나서 현재 Ki번째로 작은 나무의 높이가 무엇인지를 알고 싶다.

하지만 꿈이 너무 컸던 경근이는 감당할 수 없는 수의 콩나무를 심어버리고 말았다. 당신은 경근이를 도와 비료를 주면서 콩나무를 관찰하는 일을 해야한다.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 5개의 정수로 나타내어지며, 이를 나타내는 N, D (1 ≤ N, D ≤ 100,000), s, a, b (0 ≤ s, a, b ≤ 100,000) 가 공백으로 구분되어 주어진다.

Ci와 Ki는 s, a, b를 이용해서 생성할 수 있으며 그 방법은 아래와 같다.

for (int i=1; i<=D; i++) {
    Ci = s % N + 1;
    s = (s * a + b) % 1000000007;
    Ki = s % N + 1;
    s = (s * a + b) % 1000000007;
}

출력

각 테스트 케이스당 한 줄에 D일 동안 측정된 나무 높이들의 합을 출력한다.

예제 입력

3
5 5 4 4 4
5 5 3 3 3
5 5 2 2 2

예제 출력

35
30
22

힌트

출처

Contest > Coder's High > Coder's High 2014 J번

  • 문제의 오타를 찾은 사람: adream
  • 문제를 만든 사람: august14