概要

\(K\) 回の伝達後に「どの人たちの値が同じ場所で XOR されるか」だけが重要です。
高橋君は人々をいくつかのグループに分け、各グループの XOR の総和から最大のものを引いた値を最大化する問題になります。

考察

まず、伝達操作を \(K\) 回行った後の状態を考えます。

各人 \(i\) の値は、1 回の操作で \(A_i\) に送られます。
したがって \(K\) 回後には、人 \(i\) の初期値は \(A\) を \(K\) 回たどった先に届きます。

つまり、最終的に同じ人に届く初期値たちは XOR でまとめられます。
これは「人々をいくつかのグループに分け、各グループごとに XOR を取る」ことと同じです。

例えば、あるグループ \(G\) に含まれる人たちの初期値の XOR を

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

とします。

このとき、最終的な総和は

\[ \sum_G X_G \]

です。

次に、青木君の操作を考えます。
青木君はちょうど 1 人の初期値を任意の非負整数に書き換えられます。

あるグループ \(G\) の中の人を 1 人選んで値を書き換えると、そのグループの XOR 値 \(X_G\) だけを任意の値に変えることができます。
なぜなら、書き換え後の値をうまく選べば、グループ全体の XOR を好きな値にできるからです。

青木君は総和を最小化したいので、選んだグループの XOR を \(0\) にします。
そのため、青木君は XOR 値が最大のグループを選びます。

よって、あるグループ分けに対する最終結果は

\[ \sum_G X_G - \max_G X_G \]

になります。

あとは、高橋君がこの値を最大化するようにグループ分けを選べばよいです。

重要なのは、高橋君は任意のグループ分けを実現できることです。
各グループごとに代表者を 1 人選び、グループ内の全員の送り先をその代表者にすれば、\(K \geq 1\) なので全員が最終的に代表者に集まります。

したがって、問題は次のように言い換えられます。

\(N\) 個の値 \(V_i\) をいくつかのグループに分ける。
各グループの XOR の総和から、その最大値を引いた値を最大化せよ。

\(N \leq 12\) と小さいため、すべてのグループ分けを全探索できます。

アルゴリズム

DFS で集合分割を列挙します。

現在までに処理した人たちについて、各グループの XOR 値を bx に持ちます。
次の人 idx を処理するとき、以下のどちらかを試します。

1. 既存のグループに入れる
2. 新しいグループを作る

各グループの XOR の総和も sum として管理します。

人 idx の値を val とすると、既存グループ i に追加する場合、

• 追加前の XOR: old = bx[i]
• 追加後の XOR: nw = old ^ val

なので、総和は

\[ sum - old + nw \]

に更新されます。

すべての人をグループに入れ終わったら、現在のグループ XOR の最大値を mx として、

\[ sum - mx \]

を答え候補にします。

これを全てのグループ分けについて行い、最大値を答えます。

なお、コードでは最初に人 \(1\) を最初のグループに入れた状態から DFS を開始しています。
これは、グループの並び順による重複を避けるためです。

計算量

集合分割の個数はベル数で表されます。
\(N = 12\) のとき、ベル数は \(4,213,597\) なので十分間に合います。

• 時間計算量: \(O(N B_N)\)
  
  • \(B_N\) は \(N\) 個の要素の集合分割数
• 空間計算量: \(O(N)\)

実装のポイント

• \(K\) は入力で与えられますが、\(K \geq 1\) であれば任意のグループ分けを実現できるため、実際の計算では使いません。

• XOR 値や総和は long long で扱います。

• DFS 中に bx[i] を変更したら、再帰から戻るときに必ず元に戻します。

• sum を毎回計算し直すと遅くなるため、グループに追加したときの差分で更新します。

  ソースコード

#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;
}

---

この解説は gpt-5.5-high によって生成されました。