要素数 K の集合 (next combination) Scala編（paizaランク A 相当）

説明

要素数 N の集合から、要素数 K の部分集合をより高速に列挙することを目指します。
前回の問題では、ビット全探索ですべての部分集合を列挙して、その中から要素数 K 個のものだけを取り出して調べていました。
この方法でも正しく列挙できますが、要素数 K 以外の部分集合もすべて列挙するのであまりスマートではありません。
要素数 K 個の部分集合のみをうまく高速に列挙する方法を考え、問題に解答しましょう。

以下に実装方法を記述します。これを参考に実装してみましょう。
1 以上 N 以下の整数からなる集合 S の部分集合のうち、要素数が K のものをすべて列挙できれば良いです。
部分集合を表すビット列を T とし、T の下位 i ビット目が 1 であるとき i が含まれるとします。
以下に処理手順を参考に実装してみましょう。

1. 下 K 桁がすべて 1、他は 0 であるビット列を T とします。
2. すべての部分集合を列挙するまで 3. ~ 8. の処理を繰り返します。
3. T が表す部分集合の XOR 和を計算し、問題の答えを更新します。
4. 次の部分集合に遷移します。X の 1 である桁のうち、最下位の桁を r とします。
5. T の 0 である桁のうち、r 以上で最下位の桁を l とします。
6. T の r より上位かつ l 以下の桁に含まれる 1 の個数を c とします。
7. y = T + (下から r 桁目のみが 1 であるビット列)、z = (下 c 桁がすべて 1、他は 0 であるビット列) とします（ビット列同士の足し算は 2 進数と同様に定義されるものとします）。
8. T = (y と z のビット毎の論理和) と更新します。

例えば、N = 3、K = 2 のときは以下のように処理されます。
最初 T = 011 です。
また、最下位の桁を下から 0 桁目とすると、r = 0、l = 2、c = 1 です。
y = 100、z = 001 であり、T = 100 OR 001 = 101 と更新されます。
これを要素数 K の部分集合がすべて列挙できるまで繰り返します。

問題

この問題は、前回の問題と同じです。
上記の方法を用いてより効率よく解いてみましょう。

長さ N の数列 A = (A_1, A_2, ... A_N) が与えられます。
数列 A から K 個の整数を選んだ時、選んだ整数の XOR 和の最大値を求めてください。