Codechef WEASELTX 做题记录

原题链接

给一棵 $n$ 个点的有根树，节点 $1$ 是根。节点 $i$ 的初始权值为 $w_i$。 定义一次操作是对于每个 $i$，将 $w_i$ 修改成操作前 $i$ 的子树的所有权值的异或和。 有 $q$ 次独立的询问，每次询问是求 $t_i$ 次操作后 $w_1$ 的值。

$1\le n,q\le 2\times 10^5$，$1\le w_i,t_i\le 10^9$。

首先不难发现由于每一次操作相当于做前缀和，所以同一层上的点要么都有贡献，要么都没贡献。那么设 $f_{i,j}$ 表示第 $i+1$ 次操作之后深度为 $j$ 的点是否有贡献，显然 $f_{0,j}=1$。

稍加思考可以发现递推式 $f_{i,j}=f_{i-1,j}\operatorname{xor} f_{i,j-1}$，因为第 $j$ 层的点对第 $j-1$ 层的点有贡献。

画出转移图：

旋转 $45\degree$：

所以说 $f_{i,j}\equiv C_{i+j}^j\pmod 2$。

或者说其实这个递推式相当于求从左上角只能向下向右走走到 $(i,j)$ 的方案数，一共有 $i+j$ 次操作，其中有 $j$ 次向下。

然后根据 Lucas 定理，$C_{n}^m\equiv C_{n\operatorname{mod} 2}^{m\operatorname{mod} 2}\times C_{\lfloor\frac{n}{2}\rfloor}^{\lfloor\frac{m}{2}\rfloor}\pmod 2$，那么对于 $n,m$ 二进制第 $i$ 位 $x,y$，当 $x=0,y=1$ 时这一位就会让乘积变成 $0$，所以 $f_{i,j}=1$ 当且仅当 $i+j\operatorname{and}j=j$，即 $i\operatorname{and} j=0$。

那么求出 $a_i$ 表示所有深度为 $i$ 的点的点权的异或和，$sum_i=\operatorname{xor}_{j\operatorname{and} i=j} a_j$，那么 $t$ 次操作之后的答案就相当于是 $sum_{(t-1)二进制按位取反的结果}$。

注意 $t=0$ 的情况要特判。