zak 的随手构造

今天 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 给出了随手的构造叉掉了我的做法：

以下先提出一个问题：

给定 $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

的等价类的异或和都不变，所以构造成立。

文章操作