프로그램 최적화

다음 C++ 코드를 생각하자.

#include <algorithm>
#include <random>

int query_mex(const int *a, int l, int r);

int simulate(int n, int *a, int q, int k, int s) {
  std::mt19937 gen;
  gen.seed(s);
  int last = 0;
  while (q--) {
    int op = gen() % k;
    int i = (gen() + last) % n;
    if (!op && i) {
      std::swap(a[i - 1], a[i]);
    } else {
      int j = gen() % n;
      last ^= query_mex(a, std::min(i, j), std::max(i, j));
    }
  }
  return last;
}

이 프로그램에서 query_mex(a, l, r)은 $a_l, a_{l + 1}, \dots, a_r$에 등장하지 않는 최소 음이 아닌 정수를 반환한다.

$n$, $a$, $q$, $k$, $s$의 값이 주어질 때, 함수가 반환하는 값을 구하자.

첫째 줄에 네 정수 $n$, $q$, $k$, $s$가 주어진다. ($1 \leq n \leq 2\times 10^5$, $1 \leq q \leq 10^7$, $1 \leq k \leq 10^9$, $0 \leq s \leq 10^9$) 둘째 줄에 $n$개의 서로 다른 정수 $a_0, a_1, \dots, a_{n - 1}$이 주어진다. ($0 \leq a_i < n$)

함수가 반환하는 값을 정수로 출력한다.