《灵茶八题》题目列表

仅仅是几个字的区别，会导致截然不同的做法，也许这就是算法之美吧！

题单合集

注：下标从 0 开始。二进制的最低位是第 0 位。

考虑 a[i] 对答案的贡献：

子数组 +w+ 子数组元素和的元素和：包含 a[i] 的子数组的左端点有 i+1 个，右端点有 n-i 个，根据乘法原理，有 (i+1)\cdot(n-i) 个子数组包含 a[i]，所以 a[i] 对答案的贡献为 (i+1)\cdot(n-i)\cdot a[i]。
子数组 ^w^ 子数组异或和的异或和：同上。更强的结论是：
- 当 n 是偶数时，i+1 和 n-i 必定一奇一偶，所以 (i+1)(n-i) 是偶数，答案为 0。
- 当 n 是奇数时，如果 i 为奇数，那么 i+1 和 n-i 都是偶数；如果 i 为偶数，那么 i+1 和 n-i 都是奇数，所以只有 i 为偶数时 (i+1)(n-i) 才是奇数。所以，答案为所有偶数下标的 a[i] 的异或和。
子序列 +w+ 子序列的元素和的元素和：包含 a[i] 的子序列有 2^{n-1} 个。所以 a[i] 对答案的贡献为 2^{n-1}\cdot a[i]。所以答案为 2^{n-1}\cdot \sum a[i]。
子序列 ^w^ 子序列的异或和的异或和：
- 当 n=1 时，答案为 a[0]。
- 当 n\ge 2 时，由于 2^{n-1} 是偶数，所以答案为 0。

子数组 ^w+ 子数组异或和的元素和：
- 提示：如果数组中只有 0 和 1，要怎么做？
- 相当于计算有多少个子数组，异或和等于 1。
- 计算前缀异或和数组 s（长为 n+1），相当于从 s 中选两个数，异或等于 1。
- 这两个数必须恰好一个是 1，另一个是 0。
- 假设 s 中有 c 个 1，那么就有 n+1-c 个 0，所以答案为 c\cdot(n+1-c)。
- 一般地，统计 s 中第 k 位的 1 的个数 c，那么这一位对答案的贡献是 c\cdot(n+1-c)\cdot 2^k。
子序列 ^w+ 子序列异或和的元素和：
- 如果第 k 位都是 0，那么对答案的贡献是 0。
- 如果第 k 位有 c 个 1，用数学归纳法可以证明，从 c 个数中选偶数个数的方案数是 2^{c-1}，选奇数个数的方案数也是 2^{c-1}。再算上 0，那么异或和为 0 的子序列有 2^{n-1} 个，异或和为 1 的子序列也有 2^{n-1} 个，所以这一位的贡献是 2^{n-1}\cdot 2^k。