Overview

Only “which people’s values are XORed together at the same location” after \(K\) transmissions is important.
The problem reduces to Takahashi partitioning the people into several groups to maximize the sum of the XOR sums of each group minus the maximum among them.

Analysis

First, let’s consider the state after performing the transmission operation \(K\) times.

The value of each person \(i\) is sent to \(A_i\) in one operation.
Therefore, after \(K\) operations, the initial value of person \(i\) will reach the person obtained by following \(A\) \(K\) times.

In other words, the initial values that eventually reach the same person are aggregated using XOR.
This is equivalent to “partitioning the people into several groups and taking the XOR sum for each group.”

For example, let the XOR sum of the initial values of the people in a group \(G\) be

\[ X_G = \bigoplus_{i \in G} V_i \]

Then, the final sum is

\[ \sum_G X_G \]

Next, let’s consider Aoki’s operation.
Aoki can rewrite the initial value of exactly one person to any non-negative integer.

By choosing one person in a group \(G\) and rewriting their value, Aoki can change only that group’s XOR sum \(X_G\) to any value.
This is because, by choosing the rewritten value appropriately, the XOR sum of the entire group can be set to any desired value.

Since Aoki wants to minimize the sum, he will make the XOR sum of the chosen group \(0\).
Therefore, Aoki will choose the group with the maximum XOR sum.

Thus, the final result for a given partition is

\[ \sum_G X_G - \max_G X_G \]

The remaining task is for Takahashi to choose a partition that maximizes this value.

The key point is that Takahashi can realize any partition.
By choosing one representative for each group and setting the destination of everyone in that group to this representative, since \(K \geq 1\), everyone will eventually gather at the representative.

Therefore, the problem can be rephrased as follows:

Partition \(N\) values \(V_i\) into several groups.
Maximize the sum of the XOR sums of each group minus the maximum of these XOR sums.

Since \(N \leq 12\) is small, we can search all possible partitions.

Algorithm

We can enumerate all set partitions using DFS (Depth-First Search).

For the people processed so far, we maintain the XOR sum of each group in bx.
When processing the next person idx, we try one of the following:

1. Add them to an existing group
2. Create a new group

We also maintain the sum of the XOR sums of each group as sum.

Let the value of person idx be val. When adding them to an existing group i:

• XOR before addition: old = bx[i]
• XOR after addition: nw = old ^ val

so the sum is updated to

\[ sum - old + nw \]

Once all people have been assigned to groups, we find the maximum group XOR sum mx and consider

\[ sum - mx \]

as a candidate for the answer.

We perform this for all partitions and output the maximum value.

Note that in the code, the DFS starts with person \(1\) already placed in the first group.
This is to avoid duplicate searches caused by the permutation of groups.

Complexity

The number of set partitions is represented by Bell numbers.
For \(N = 12\), the Bell number is \(4,213,597\), which is small enough to run well within the time limit.

• Time Complexity: \(O(N B_N)\)
  
  • \(B_N\) is the Bell number of \(N\) elements.
• Space Complexity: \(O(N)\)

Implementation Points

• Although \(K\) is given in the input, as long as \(K \geq 1\), we can realize any partition, so we do not use it in the actual calculation.

• XOR sums and the total sum should be handled using long long.

• If you modify bx[i] during DFS, make sure to revert it back to its original state when returning from the recursion.

• Recalculating sum from scratch every time would be too slow, so we update it incrementally by calculating the difference when adding to a group.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<long long> V(N);
    for (auto &x : V) cin >> x;

    long long bx[12] = {};
    long long ans = 0;

    bx[0] = V[0];

    auto dfs = [&](auto&& self, int idx, int bcnt, long long sum) -> void {
        if (idx == N) {
            long long mx = 0;
            for (int i = 0; i < bcnt; i++) mx = max(mx, bx[i]);
            ans = max(ans, sum - mx);
            return;
        }

        long long val = V[idx];

        for (int i = 0; i < bcnt; i++) {
            long long old = bx[i];
            long long nw = old ^ val;
            bx[i] = nw;
            self(self, idx + 1, bcnt, sum + nw - old);
            bx[i] = old;
        }

        bx[bcnt] = val;
        self(self, idx + 1, bcnt + 1, sum + val);
    };

    dfs(dfs, 1, 1, V[0]);

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.