E - メッセージの伝達 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

N 人の人がおり、それぞれ 1 から N までの番号が付いています。各人 i は初期値として非負整数 V_i を持っています。

高橋君は「伝達ネットワーク」を設計します。伝達ネットワークとは、各人 i に対して送り先 A_i（1 以上 N 以下の整数、A_i = i も許される）を定めた配列 A = (A_1, A_2, \ldots, A_N) のことです。

伝達ネットワークが定まると、「伝達操作」を行うことができます。1回の伝達操作は以下のように行われます：

  • すべての人が同時に、自分の持つ値を送り先に送る。すなわち、人 i は自分の操作前の値を人 A_i に送る。
  • 操作後、各人 j の新しい値は、j に値を送ったすべての人の操作前の値のビットごとの排他的論理和（XOR）となる。すなわち、人 j の新しい値は A_k = j を満たすすべての k について V_k（操作前の値）の XOR である。A_k = j を満たす k が存在しない場合、人 j の値は 0 になる。

高橋君と青木君は、以下の手順でゲームを行います：

  1. 高橋君が配列 A（各 A_i は 1 以上 N 以下の整数）を決める。
  2. 青木君が配列 A の内容を確認した上で、ちょうど 1 人を選び、その人の初期値を任意の非負整数に書き換える。（必ず 1 人を選ばなければならないが、元と同じ値に書き換えることは許される。つまり実質的に書き換えない場合と同じ状態にすることも可能である。）
  3. 伝達操作をちょうど K 回行う。
  4. すべての人の値の総和を計算する。

高橋君はこの総和を最大化したいと考え、青木君はこの総和を最小化したいと考えています。

両者が最適に行動したとき、K 回の伝達操作後のすべての人の値の総和を求めてください。

注記

ビットごとの排他的論理和（XOR）とは、二つの非負整数を二進法で表したとき、各桁について一方のみが 1 であれば 1、そうでなければ 0 とする演算です。複数の値の XOR は、これを順に適用して得られます（結合的であるため順序によらず結果は同じです）。値が 1 つだけの場合の XOR はその値自身、値が 0 個の場合の XOR は 0 と定めます。

制約

  • 1 \leq N \leq 12
  • 1 \leq K \leq 10^{18}
  • 0 \leq V_i \leq 10^{9}
  • 入力はすべて整数である。

入力

N K
V_1 V_2 \ldots V_N
  • 1 行目には、人数を表す整数 N と、伝達操作の回数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各人の初期値を表す整数 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。

出力

両者が最適に行動したときの、K 回の伝達操作後のすべての人の値の総和を 1 行で出力せよ。

入力例 1

3 2
1 2 3

出力例 1

3

入力例 2

4 1
0 5 7 10

出力例 2

12

入力例 3

8 17
12 34 56 78 90 123 456 789

出力例 3

849

入力例 4

12 123456789012345678
1000000000 999999937 123456789 987654321 0 1 2 3 255 1024 65535 314159265

出力例 4

2425337132

入力例 5

1 1000000000000000000
1000000000

出力例 5

0

Score : 433 pts

Problem Statement

There are N people, numbered 1 to N. Each person i initially has a non-negative integer value V_i.

Takahashi will design a "transmission network". A transmission network is defined by an array A = (A_1, A_2, \ldots, A_N) of length N, where each A_i is an integer between 1 and N (inclusive), representing the destination for person i (it is allowed that A_i = i).

Once the transmission network is determined, "transmission operations" can be performed. One transmission operation is carried out as follows:

  • All people simultaneously send their current values to their destinations. That is, person i sends their pre-operation value to person A_i.
  • After the operation, the new value of each person j becomes the bitwise exclusive OR (XOR) of the pre-operation values of all people who sent their values to j. That is, the new value of person j is the XOR of V_k (the pre-operation value) for all k such that A_k = j. If there is no k satisfying A_k = j, the value of person j becomes 0.

Takahashi and Aoki play a game using the following procedure:

  1. Takahashi decides the array A (where each A_i is an integer between 1 and N inclusive).
  2. Aoki inspects the contents of the array A, chooses exactly one person, and rewrites their initial value to an arbitrary non-negative integer. (Aoki must choose exactly one person, but rewriting to the same value as the original is allowed. In other words, he can choose to leave the value practically unchanged.)
  3. The transmission operation is performed exactly K times.
  4. The sum of the values of all people is calculated.

Takahashi wants to maximize this sum, and Aoki wants to minimize this sum.

Find the sum of the values of all people after K transmission operations when both players play optimally.

Notes

The bitwise exclusive OR (XOR) of non-negative integers is an operation where, when two non-negative integers are represented in binary, the result has a 1 in each digit if and only if exactly one of the two numbers has a 1 in that digit, and 0 otherwise. The XOR of multiple values is obtained by applying this operation sequentially (since it is associative, the order does not affect the result). The XOR of a single value is the value itself, and the XOR of zero values is defined as 0.

Constraints

  • 1 \leq N \leq 12
  • 1 \leq K \leq 10^{18}
  • 0 \leq V_i \leq 10^{9}
  • All input values are integers.

Input

N K
V_1 V_2 \ldots V_N
  • The first line contains an integer N representing the number of people, and an integer K representing the number of transmission operations, separated by a space.
  • The second line contains integers V_1, V_2, \ldots, V_N representing the initial values of each person, separated by a space.

Output

Print the sum of the values of all people after K transmission operations when both players play optimally in a single line.

Sample Input 1

3 2
1 2 3

Sample Output 1

3

Sample Input 2

4 1
0 5 7 10

Sample Output 2

12

Sample Input 3

8 17
12 34 56 78 90 123 456 789

Sample Output 3

849

Sample Input 4

12 123456789012345678
1000000000 999999937 123456789 987654321 0 1 2 3 255 1024 65535 314159265

Sample Output 4

2425337132

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

0