zak 的随手构造

konyakest · 2025-02-08 17:04:59 · 个人记录

今天 zak 来讲题讲到了 [ABC274Ex] XOR Sum of Arrays 。

给出一个序列 a，询问：

• 提取出 [l_1,r_1],[l_2,r_2],[l_3,r_3] 这三个区间，考虑每一位，对位异或和是否都为 0。

我提出了这样一个算法：

随机几个 len,k，设 b_i 为 a_i 按照 len 的长度循环左移 k*i 位的结果，维护 b 的异或和，判断时直接判断 b 的异或和是否相同。

后来这个算法通过了 atcoder 的数据并跑到了 luogu 次优解。

然后，zak 给出了随手的构造叉掉了我的做法：

• a_i=[x^i]\prod_{i=1}^{64}(1+x^i) \mod 2

以下先提出一个问题：

给定 n，构造一个无穷长的序列，这个序列只有前有限项的值可能为 1，之后都是 0，且对于任意 0\le i<j\le n, \oplus a_{kj+i}=0。

要求上述“前有限项”长度 \le n^2，且不能全为 0。

不难发现，这个构造题可以卡掉我的构造。

构造：a_i=[x^i]\prod_{i=1}^{n}(1+x^i) \mod 2

解释：

考虑每个 i：

你发现这个串是 1+x^i 的倍数，相当于你用相差 i 的两个数（比如 i=2 时，即为 101）去“拼”他可以把这个串异或成 0。

注意到每次去拼的时候，每个模 i 余 j 的等价类的异或和都不变，所以构造成立。