题解

思路

固定操作次数 $k$，把异或看成模 $2$ 的逐位加法。

做法

重复做一维前缀和后，初始的 $A_i$ 对最终 $A_N$ 的贡献次数为 $\binom{N-i+k-1}{k-1}$。由 Lucas 定理，这个组合数为奇数当且仅当 $(N-i)\mathbin{\&}(k-1)=0$，因此答案是所有满足该条件的 $A_i$ 的异或。

取不小于 $\max(N,M)$ 的最小二次幂 $S$，令 $x=N-i$，再令 $y=S-1-x$。由于 $S-1$ 的低位全为 $1$，条件等价于 $k-1$ 的所有置位都包含在 $y$ 中。把 $A_i$ 放到下标 $y$，对数组做“超集异或和”高维前缀和：枚举每一位，将含有该位的状态异或到不含该位的状态。变换后下标 $k-1$ 的值就是第 $k$ 个答案。

复杂度

时间复杂度为 $O(S\log S)$，空间复杂度为 $O(S)$。