打卡题进阶版。

在评价题目中看见很多人用了“结论题”这个标签，自习想想也对，赛后讲解没懂，同学给我讲的时候我很懵，突然会了后感觉这题没这么难，我现在在写题解，除了直接写做法好像写不出来什么思考过程。

把题目要求的变形一下，定义数组 $s$ 为前缀和，那么题目会变成这样（注意从 $0$ 开始）：

$\bigoplus_{i=0}^ns_n-s_i$

我们可以发现，这是一个关于 $s_n$ 的函数。

观察到模数是 $2$ 的整数次幂，我们直接建立 $21$ 个树状数组大小分别为 $2,4,8,16\dots2^{21}$ ，第 $k$ 个树状数组维护 $s_i$ 的后 $k$ 位组成的桶子。

对于答案中的每一位，我们可以在对应的桶子中计算与 $s_n$ 的差恰好在当前为是 $1$ 的数的个数即可。

具体一点：

$ans=\sum_{i=0}^{20}\sum_{j=s_n\,\text{mod}\,2^{i 1} 1}^{s_n\,\text{mod}\,2^{i 1} 2^i}box_{i,j}\,\text{mod}\,2^{i1}$

代码不是特别难写（相比 I）。

题解 | #D

强推我的洛谷博客（或者说文章区）