思路
考虑转化成组合数学
一个数最终会被异或多少次, 等价于在给出的网格图中, 有多少种路径走到这个位置
显然是一个 \(\displaystyle {a \choose b}\) 的组合数形式
又有
\[{a \choose b} \bmod 2 = [a \,\&\, b = b]
\]
不难发现若确定 \(a\), 我们直接枚举 \(a\) 子集就可以 \(\mathcal{O} (2^{\text{popcount}(a)})\) 做一次
考虑优化
若用第 \(t\) 行来计算, 对于 \((t, i)\) 对 \((x, y)\) 的贡献是 \(\displaystyle {x - t \choose i - y}\)
若我们让 \(t = x \bmod 512\), 则只用 \(\mathcal{O} (nB)\) 预处理, 后面的 \(\mathcal{O} (2^{\text{popcount}(x - t)})\) 为原来的根号级别
总复杂度是一个根号分治级别的 \(\mathcal{O} (n \sqrt{n} + q \sqrt{n})\)
#include <bits/stdc++.h>
#define int long longconst int MAXN = 3e5 + 10;int a[MAXN];
int n, q;
int b[520][MAXN];signed main() {scanf("%lld", &n);for (int i = 0; i < n; i++) {scanf("%lld", &a[i]);b[0][i] = a[i];}for (int i = 1; i < 512; i++) for (int j = 0; i + j < n; j++) b[i][j] = b[i - 1][j] ^ b[i - 1][j + 1];scanf("%lld", &q);while (q--) {int x, y;scanf("%lld%lld", &x, &y);if (x < 512) {printf("%lld\n", b[x][y]);} else {int t = x % 512;int ans = b[t][y];for (int yy = x - t; yy; yy = (yy - 1) & (x - t)) {if (t + y + yy < n)ans ^= b[t][y + yy];}printf("%lld\n", ans);}}return 0;
}
总结
观察力过于敏锐了
找到令 \(t = x \bmod 2^p\) 的性质之后, 我们可以用少的 \(p\) 来降低大量的 \(\mathcal{O} (2^{\text{popcount}(x - t)})\), 而且前面的 \(\mathcal{O} (n2^p)\) 预处理也可以接受