题解

思路

固定 $a_i$。由递推式与杨辉三角可知，它对 $b_{j,n}$ 的贡献次数为

只关心次数的奇偶性。由 Lucas 定理，上式为奇数当且仅当

令 $m$ 为不小于 $n$ 的最小二次幂，$M=m-1$。把未知数组放到长度为 $m$ 的数组 $A$ 中，令 $A_{n-i}=a_i$，其余位置暂置零。再令

则完整的 $B$ 正是 $A$ 的子集 Zeta 变换。异或意义下，Zeta 变换做两次就是恒等变换，因此若完整 $B$ 已知，只需再做一次相同变换即可恢复 $A$。

困难在于只知道 $B$ 的 $n$ 个位置。设 $C$ 是已知部分按补集下标排列后做一次 Zeta 变换的结果。先把对应未知 $B$ 的约束位置在 $C$ 中清零，再做一次 Zeta 变换，就能补出全部未知的 $B$。最后对完整 $B$ 做第三次 Zeta 变换，取出 $A_{n-i}$。

这个过程同时证明线性变换可逆，所以输入总有唯一解。

做法

子任务一

对每个二进制位独立枚举 $a$ 的 $2^n$ 种零一取值，按 Lucas 条件检查全部 $b_{j,n}$，找到唯一可行掩码。把三十个二进制位合并为答案。

子任务二

当 $n$ 是二次幂时 $m=n$，完整的 $B$ 没有未知位置。将给定序列按补集下标放置后，直接做一次异或 Zeta 变换即可恢复 $A$。

子任务三

把每个 $a_i$ 看成一个同时携带三十个二进制位的 GF(2) 未知量。用 Lucas 条件建立 $n\times n$ 系数矩阵，使用位集加速高斯消元；行异或时右端整数也整体异或，一次即可处理三十位。

满分做法

1. 取 $m$ 为不小于 $n$ 的最小二次幂，把给定值写入 $B_{M\oplus(j-1)}$。
2. 将已知部分按补集下标放入辅助数组，对辅助数组做一次子集 Zeta 变换。
3. 把与未知 $B$ 位置对应的约束清零，再做一次 Zeta 变换并补齐 $B$。
4. 对完整 $B$ 做一次 Zeta 变换，输出 $A_{n-i}$。

复杂度

子任务一的时间复杂度为 $O(30\cdot2^n n^2)$，空间复杂度为 $O(n)$。

子任务二和满分做法的时间复杂度为 $O(m\log m)$，空间复杂度为 $O(m)$。

子任务三的时间复杂度为 $O(n^3/64)$，空间复杂度为 $O(n^2/64)$。