模拟赛 15 题解

前缀和+stl + dp + 优化 +树链剖分

A.计算异或和

我们可以纵向看这些式子：

${\Huge{\oplus}}_{i=1}^n{\Huge{\oplus}}_{j=1}^n j\%i$

那么我们发现，对一个固定的数取模是有循环节的，这个循环节个数为 $\lfloor\frac n i\rfloor$。

由于进行的是异或操作，所以只有个数为奇数时才被算入答案。

贡献是完全剩余系的异或和，即 $[0,i-1]$ 。

关注循环节不完全包含 $n$ 的情况，即 $n\neq 0\mod i$。

B.配置香水

做一遍前缀和，问题转化为选出两个数，使得差是 $k$ 的倍数。

我们可以直接枚举左端点和 $k$ 的倍数，用 $map$ 统计答案，复杂度是 $O(n\log n\log_k \sum n)$ 的。

可以用 $Hash$ 表省去一个 $\log$ 。

C.奥法之劫

点这里

D.多彩树

可以用树剖或 LCT 实现。先咕着