Problem F: MLE

ICPC World Finals 4日目

暗い嵐の夜だった。 夢の中でティー氏はタイムスリップしていた。 ICPCの会場のようだが何かおかしい…。 もしや…これは、N年前（Nは自然数）のICPCなのか…? 混乱の内に競技は開始してしまった。 だが慌てる必要はない。 きっと問題も簡単に違いない。 例えばこれなどはソートするだけで解けてしまうはずではないか。 冷静にコードを書き上げ、速やかにSubmit。

しかしその結果は…Memory Limit Exceeded…?!

問題

C++言語については以下のコード

long long int a[n];
unsigned long long int x = x0;
for (int i = 0; i < n; i++) {
  a[i]=(long long int)x;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
}

Java言語については以下のコード

long[] a = new long[n];
long x = x0;
for(int i = 0; i < n; i++){
  a[i] = x;
  x ^= x << 13;
  x ^= x >>> 7;
  x ^= x << 17;
}

で与えられる擬似乱数列$a[0], a[1], \cdots, a[n-1]$を昇順にソートする。 $k$番目の数（$a[k-1]$）を答えよ。

入力

n k x0

1行目に 擬似乱数列の長さ$n$、 求めるインデックス$k$、 コード中の初期値$x0$ が空白区切りで与えられる。

出力

問題文にて定義された擬似乱数列において$k$番目に小さい数を1行に出力せよ。

制約

• $0 \leq x0 \leq 9$
• $1 \leq n \leq 10^{8}(= 100000000)$
• $1 \leq k \leq n$

入出力例

入力1

20 10 1

出力1

-768720241707614171

この入力において生成される数列は以下の通りである。

1
1082269761
1152992998833853505
-7269227409276787159
-768720241707614171
-8787613929710185883
-670945072575735807
-6753709453369041295
-4166779903597258483
9024654201992055039
8332670729032836398
2074683623940568804
-1176172910426220663
5632491372296299238
-8006175397324373085
-8536891001451786268
-3486562341448986757
1956468987595729445
-6260278484400246991
1076885984028793263

入力2

1000000 100 2

出力2

-9221458681145860019

入力3

100000000 10000000 3

出力3

-7379326796154077070