题解 | #异或疑惑#

D题个人题解

将操作视为连边，形成若干个连通块。

考虑将这 个数看作同一连通块，造成的和的下界必然是这 个数的异或。（可以手模拆位思考证明一下）

对于这个连通块可得到的和，我们总能用 次操作得到同样的和。对于即将成环的连边，我们可以在这一路径上全都异或同样的值达成同样的效果，如此反悔使得不可能存在环。

记连通块的异或值为 ，连通块的和为 。

若 大于等于 ，我们总能使 ， 为任意非负整数。构造出 个 和 个 后，任选 个 异或 即可。

若 等于 ，则无法操作，。

若 等于 ，可以发现，对于二进制下 为 的位置可以造成 或 的贡献， 的位置只能是 。

考虑存在多个连通块，需要的总操作次数是 。我们知道，将一个数组划分成若干个集合的方案总数是贝尔数，这一概念与划分成若干个连通块的方案数等价。数组大小为 的贝尔数是 ，我们可以枚举所有方案。

接下来只需解决如何检查每组方案是否可行即可。我们记录每个连通块的下界和：

• 下界和必须与 同奇偶。
• 若存在某个连通块大小大于等于 ，那么下界和小于等于 即可。
• 否则需要检查连通块大小为 造成的贡献：对于 减去下界和 的余量记为 。记录每一个大小为 的连通块能造成 贡献的数位，之后从低位到高位枚举检查当前位是否能满足 的要求即可。

以下是代码：

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    ll XA = 0;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        XA ^= a[i];
    }
    if ((XA & 1) != (k & 1)) {
        cout << -1 << endl;
        return;
    }
    if (n == 1) {
        cout << (a[0] == k ? 0 : -1) << endl;
        return;
    }

    int ans = 101;
    vector<int> g(n);//表示当前数在第几个集合
    function<void(int, int)> dfs = [&](int id, int m) -> void {
        if (id == n) {
            ll DL = 0;//下界和
            vector<ll> X(m);//连通块异或和
            vector<int> cnt(m);//连通块大小
            for (int i = 0; i < n; i++) {
                X[g[i]] ^= a[i];
                cnt[g[i]]++;
            }
            
            bool U = false;//是否有大小大于等于3的连通块
            for (int i = 0; i < m; i++) {
                DL += X[i];
                if (cnt[i] == 1) 
                    continue;
                if (cnt[i] > 2)
                    U = true;
            }

            if (DL > k) 
                return;
            
            if (U)
                ans = min(ans, n - m);

            vector<int> add(60);
            for (int i = 0; i < m; i++) {
                if (cnt[i] != 2)
                    continue;
                for (int j = 0; j < 60; j++) {
                    if (!(X[i] >> j & 1))
                        add[j + 1]++;
                }
            }

            ll rest = k - DL;
            for (int b = 0; b < 60; b++) {
                if (rest >> b & 1) {
                    if (add[b] == 0)
                        return;
                    add[b]--;
                }
                if (b + 1 < 60) {
                    add[b + 1] += add[b] / 2;
                    add[b] %= 2;
                }
            }
            ans = min(ans, n - m);
            return;
        }

        //贝尔数方案通用枚举方式，m代表现在有多少个集合
        for (int i = 0; i <= m; i++) {
            g[id] = i;
            dfs(id + 1, m + (i == m));
        }
    };
    dfs(0, 0);

    cout << (ans == 101 ? -1 : ans) << endl;
}