「ARC217A」Min of Sum of XOR

    「ARC217A」Min of Sum of XOR

    ARC217A

    给出一个正整数 nn。

    构造一个关于 nn 的排列,使得 ∑i=1n⨁j=1ipj\sum_{i = 1}^n \bigoplus_{j = 1}^i p_j 最小。

    其中 ⨁j=1ipj\bigoplus_{j = 1}^i p_j 表示 p1,…,pip_1, \dots, p_i 的异或和。

    数据范围:1≤n≤2×1051 \leq n \leq 2\times 10^5。

    时空限制:22s / 10241024MiB。

    Solution

    首先要考虑这个问题的下界。

    不妨先思考一个子问题:对于一个长度为 nn 的 0101 序列,如何重排才可以使得前缀异或和之和最小?

    • 假设一共有 cc 个 11,应该将第 2i−12i - 1 个 11 与第 2i2i 个 11 相邻摆放。特别地,若 cc 为奇数,则最后一个 11 需要放在第 nn 位上。

    继续考虑这个问题的下界。对于每一个二进制位,都要遵循上述的摆放规则,才可以取到下界。

    回顾一个关键性质:4i,4i+1,4i+2,4i+34i, 4i + 1, 4i + 2, 4i + 3 的异或和为 00。

    并且 4i,4i+1,4i+2,4i+34i, 4i + 1, 4i + 2, 4i + 3 的所有第 kk (k≥2k \geq 2) 个二进制位全都相等。这启发我们,以 44 为步长进行分段。

    不难发现对于排列 1,…,n1, \dots, n,只有第 0,10, 1 个二进制位还不满足要求。

    将分段调整成 4i,4i+1,4i+3,4i+24i, 4i + 1, 4i + 3, 4i + 2。这样第 00 个二进制位和第 11 个二进制位段内分别为 (0,1,1,0),(0,0,1,1)(0, 1, 1, 0), (0, 0, 1, 1),即可符合要求。

    对于最后不足 44 个的一段,就直接按顺序填写剩下的数即可。

    注意到当 n≡0,1,3(mod4)n \equiv 0, 1, 3 \pmod 4 时,显然也可以取到下界。只有 n≡2(mod4)n \equiv 2 \pmod 4 这一例外,此时最后一段是不完整的。

    事实上 n≡2(mod4)n \equiv 2 \pmod 4 的时候是取不到下界的。假设存在某个排列 pp 取到了下界:

    • 因为 1,…,n−11, \dots, n - 1 中所有第 kk (k≥1k \geq 1) 个二进制位都有偶数个,此时再将 nn 加入的话,根据规则就必然有 pn=np_n = n。
    • 但是此时 1,…,n1, \dots, n 中的第 00 个二进制位有奇数个,若想取到下界必有 pnp_n 为奇数,这与 pn=np_n = n 矛盾。

    但该种情况经过上述构造可以取到下界 +1+1,所以该种构造是正确的。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    void work() {
        int n;
        std::cin >> n;
    
        std::vector<int> ans(n + 1);
        std::iota(ans.begin(), ans.end(), 0);
    
        for (int i = 3; i <= n; i += 4) {
            std::swap(ans[i - 1], ans[i]);
        }
        for (int i = 1; i <= n; i ++) {
            std::cout << ans[i] << " \n"[i == n];
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }