题解：CF2283C Big XOR

· · 题解

这是一篇特别详细的题解。

思路

考虑先把不变量求出来，而显然这道题的不变量只有 k，于是可得：

\begin{align*} k &= \bigvee_{i = 1}^n i \\ &= 2^{\log_2(n)+1}-1 \end{align*}

方便起见，令 h = \log_2(n)。

由于 m 是操作 a 后得到的 b 的异或和，根据定义有 m<2^{h+2}，又因为要求 m \le 2k，即 m \ge 2^{h+2}-2，所以：

继续分析，令：

m' = \bigoplus_{i = 1}^n i

那么假设操作的下标集合为 S，可得：

m = m' \oplus \left[\bigoplus_{i \in S} (i \oplus 2i)\right]

由于 m' 是不变量，问题转化为构造 S 使得 m 满足上述条件。

虽然该问题可以使用线性基的某种变形完成，但是这未免过于复杂了些，遂考虑简单做法。

这个时候，神之一手降临了！我们不妨大胆去做，直接删掉所有 i \not= 2^j 的 i，剩下的 i 就变成了 2 的幂。

这样做的正确性是什么呢？让我们分析一下。

先来考虑一下此时的 i \oplus 2i 有什么规律，通过手玩样例可以发现此时 i \oplus 2i 的二进制表示其实就是两个 1 加上 j 个 0。

其中 i = 2^j。

也就是说，令：

M = \bigoplus_{i \in S} (i \oplus 2i)

那么任意操作下标集合 S 所得到的 M 的集合为 \{A \oplus 2A \ | \ 0 \le A<2^{h+1}-1\}，逐位计算可得：

M_i = \begin{cases} A_i \oplus A_{i-1}, & i>0 \\ A_i, & i = 0 \end{cases}

也可以假定 A_{-1} = 0。

假设我们知道了 M，如何反推出 A 呢？

因为 M_i = A_i \oplus A_{i-1}，所以可得递归式 A_i = M_i \oplus A_{i-1}，直接使用递归式转和式的最基本的方法可以得到：

A_i = \bigoplus_{j = 0}^i M_j

由于我们留下的 i 全部都是 2 的幂，所以 A 的第 j 位等于 d_{2^j}。

这就是只保留 2 的幂的好处。

接下来就是如何求出 M，很显然我们可以得到两种 M，分别为 M_1 = m' \oplus (2^{h+2}-2) 或者 M_2 = m' \oplus (2^{h+2}-1)。

于是就出现了一个两难的问题，两者皆可，选哪一个呢？

你可能会想到两者都跑一遍检测，哪个可以就选哪个。

这其实是可行的，不过判断条件是 A_{h+1} = 0，这简直太不优雅了。

遂考虑优雅做法。

我们令 j \in \{0,1,2\}，那么 i \in \{1,2,4\}，显然此时在 S = \{1,2,4\} 的情况下 M 就是 \{3,6,12\}，写一个程序跑一下 M 的所有子集的异或和在二进制下的 \operatorname{popcount}，就可以得到一个非常惊人的结论：

:::info[当然这个结论是有严谨证明的] 首先证明：

\forall i = 2^j,\operatorname{popcount}(i \oplus 2i) \equiv 0 \pmod 2

诶等等，这似乎不需要证明了！

因为之前我们已经研究过：在 i 是 2 的幂的情况下 i \oplus 2i 在二进制下一定是两个 1 加上 j 个 0。

然后直接使用恒等式：

\operatorname{popcount}(x \oplus y) = \operatorname{popcount}(x)+\operatorname{popcount}(y)-2\operatorname{popcount}(x \land y)
由于偶数加上偶数减去偶数还是偶数，所以证完了。
也就是说 \operatorname{popcount}(M) 一定为偶数！

而 M_1 和 M_2 在二进制下的 \operatorname{popcount} 的奇偶性一定是不同的。

也就是说题目一定有解！

莫名其妙地证明了题目已经给出的条件！？

其实也变相说明了我们只需要选择 \operatorname{popcount} 为偶数的 M 进行计算即可。 :::success[Code] 关于代码中 m' 的计算方式，请看“推广”。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
bool a[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    for(int __ = 1;__<=_;++__)
    {
        int n;
        cin >> n;
        int s = n&3,nn;
        if(!s)
        {
            nn = n;
        }
        else if(s == 1)
        {
            nn = 1;
        }
        else if(s == 2)
        {
            nn = n+1;
        }
        else
        {
            nn = 0;
        }
        for(int i = 1;i<=n;++i)
        {
            a[i] = 0;
        }
        int h = 31-__builtin_clz(n),m = nn^((1<<h+2)-1),k = (1<<h+1)-1;
        if(__builtin_popcount(m)&1)
        {
            m^=1;
        }
        bool cur = 0;
        for(int i = 0;i<=h;++i)
        {
            cur^=(m>>i)&1;
            if(cur)
            {
                a[1<<i] = 1;
            }
        }
        for(int i = 1;i<=n;++i)
        {
            cout << a[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

:::

推广

其实这个题是可以推广的：

在原题的基础上将数据范围改为 1 \le n \le 10^{18}，然后把输出格式改成只输出要操作的下标。

很显然操作的下标数量是 \mathcal{O}(\log n) 级别的（上面说过了），所以输出部分不会超时。

而刚刚题目中的做法只有求 m' 才会超时，考虑优化。 :::info[如何快速求 m'？] 令：

f(x) = \bigoplus_{i = 1}^x i

然后手算几个 f 找一下规律：

f(1) = 1 \\ f(2) = 3 \\ f(3) = 0 \\ f(4) = 4

不难发现：

f(n) = \begin{cases} n, & n \equiv 0 \pmod 4 \\ 1, & n \equiv 1 \pmod 4 \\ n+1, & n \equiv 2 \pmod 4 \\ 0, & n \equiv 3 \pmod 4 \end{cases}

当然还是要证明一下的。

首先有一个非常显然的引理：

\forall i \in \N,4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0

这是因为这四个数在二进制下只有最低两位不同，而且分别是：

(00)_2,(01)_2,(10)_2,(11)_2

这四个东西异或起来就是 0，而高位又完全相同，所以是 0。

然后根据这个引理就很容易得到刚刚发现的规律了。

最后根据定义 m = f(n)。

不得不说这个方法是真的太神奇了。

然后就做完了。

总结

感觉操作类型的构造题就是先把不变量算了，先算出不操作时的数值，然后考虑操作的增量，进行一连串神秘的分析即可。

尾声

如果你也想让这篇题解被更多萌新看到，请你点一个小小的赞，助力我的文章造福更多萌新，谢谢你们！