Overview

The values obtained after \(K\) transmissions can be analyzed by decomposing them into “XORs of groups of people.”
Ultimately, this problem can be reduced to: “Divide \(N\) people into several groups, and maximize the sum of the XORs of each group minus the maximum XOR among them.”

Observations

1. The value after transmissions becomes the “XOR of each group”

Let \(f(i)=A_i\) be the function representing the destination.

After 1 transmission, the value of person \(j\) becomes the XOR of the values of all people \(i\) who satisfy:

\(A_i=j\)

Similarly, after \(K\) transmissions, the value of person \(j\) becomes the XOR of the initial values of all people \(i\) who satisfy:

\(f^K(i)=j\)

In other words, after \(K\) transmissions, each person \(i\) reaches some person, and those who share the same destination form a group.
The final value is the XOR of the initial values of the people belonging to that group.

2. Any grouping can be realized

In fact, as long as \(K \geq 1\), any grouping can be realized by some transmission network.

For example, for a certain group \(G\), we choose one representative \(r \in G\).
Then, we make everyone in the group send their value to \(r\), and \(r\) sends their value to themselves.

Then, after 1 transmission, everyone’s value will be gathered at \(r\), and will remain at \(r\) thereafter.
Therefore, we can realize the same grouping regardless of the value of \(K\).

Thus, \(K\) does not affect the answer in this problem.

3. Aoki’s operation is equivalent to “deleting one group”

Let the XOR of a group \(G\) be:

\(\bigoplus_{i \in G} V_i\)

If Aoki changes the value of one person in group \(G\), the XOR of this group can be made into any non-negative integer.
This is because by choosing the changed value appropriately, the XOR of the entire group can be adjusted to any desired value.

Since Aoki wants to minimize the sum, he will make the XOR of that group \(0\).

That is, Aoki will choose one group with the maximum XOR among the final groups and set its XOR to \(0\).

Therefore, the score for the grouping made by Takahashi will be:

\(\sum_{\text{グループ } G} \mathrm{xor}(G) - \max_{\text{グループ } G} \mathrm{xor}(G)\)

4. The problem to be solved

In the end, we just need to solve the following problem:

• Divide \(N\) people into several non-empty groups
• The value of each group is the XOR of \(V_i\) for all \(i\) in that group
• Maximize the sum of the XORs of the groups minus the maximum XOR

Since \(N \leq 12\), we can represent sets using bitmasks and use subset DP.

Algorithm

1. Precompute the XOR of each set

For the set represented by the bitmask mask, we precompute:

\(\mathrm{xor}[mask] = \bigoplus_{i \in mask} V_i\)

This can be computed in \(O(2^N)\) by removing the least significant bit one by one.

2. Fix the “group deleted by Aoki”

Let ignored be the group deleted by Aoki.

The XOR of this group is:

\(L = \mathrm{xor}[ignored]\)

For this group to be deleted as the maximum value, the XOR of all other groups must be at most \(L\).

The remaining set of people is:

\(remain = full \setminus ignored\)

We partition this remain such that the XOR of each group is at most \(L\), and maximize the sum of their XORs.

3. Subset DP

For a fixed ignored, let:

dp[mask] = the maximum sum of XORs when partitioning the people in mask into groups that satisfy the condition.

The initial value is:

\(dp[0] = 0\)

When mask is not empty, we choose a group sub that contains the least significant bit of mask.

Then,

\(dp[mask] = \max(dp[mask \setminus sub] + \mathrm{xor}[sub])\)

However, as a condition, we must have:

\(\mathrm{xor}[sub] \leq L\)

By only enumerating sub that always contains the least significant bit, we can avoid overcounting the same partition.

Finally,

dp[remain]

will be the score when ignored is deleted.

We try this for all non-empty sets ignored and take the maximum value as the answer.

Complexity

• Time Complexity: \(O(4^N)\)
• Space Complexity: \(O(3^N)\)

Since \(N \leq 12\), this runs sufficiently fast.

Implementation Details

• xors[mask] precomputes the XOR of each set.

• sublists[mask] precomputes only the subsets that contain the least significant bit of mask.

  • This prevents considering the same partition multiple times during DP transitions.

• Since ignored is the group deleted by Aoki, it must be a non-empty set.

• Although K is given in the input, it is not used in the implementation because any grouping can be realized as long as \(K \geq 1\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    V = list(map(int, input().split()))

    S = 1 << N
    full = S - 1

    xors = [0] * S
    for mask in range(1, S):
        lb = mask & -mask
        idx = lb.bit_length() - 1
        xors[mask] = xors[mask ^ lb] ^ V[idx]

    sublists = [[] for _ in range(S)]
    for mask in range(1, S):
        lb = mask & -mask
        rest = mask ^ lb
        s = rest
        arr = sublists[mask]
        while True:
            arr.append(s | lb)
            if s == 0:
                break
            s = (s - 1) & rest

    dp = [0] * S
    ans = 0

    for ignored in range(1, S):
        limit = xors[ignored]
        remain = full ^ ignored

        for mask in range(1, S):
            if mask & ignored:
                continue

            best = -1
            for sub in sublists[mask]:
                val = xors[sub]
                if val <= limit:
                    prev = dp[mask ^ sub]
                    if prev >= 0:
                        cand = prev + val
                        if cand > best:
                            best = cand
            dp[mask] = best

        if dp[remain] > ans:
            ans = dp[remain]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.