题解 AT5799 【[AGC043B] 123 Triangle】

首先进行一次绝对值差分，让序列中的数都在 $0 \sim 2$ 中，显然无论什么情况后面的每个数只可能为 $0 \sim 2$。 如果此时的序列中存在 $1$，则意味着答案只可能是 $0$ 或 $1$；如果不存在 $1$，则答案只可能是 $0$ 或 $2$。 对于不存在 $1$ 的情况，我们可以将每个数都 $\div 2$，最后再将答案 $\times 2$，这显然是等价的。 于是现在的答案都只可能是 $0$ 或 $1$ 了，于是显然我们只用在模 $2$ 的情况下讨论。 考虑一次绝对值差分在模 $2$ 意义下的影响，可以发现等价于 $\operatorname{xor}$。 现在问题变为，给定一个 $0/1$ 序列，每次将相邻两个数 $\operatorname{xor}$，求最后剩下的数。 那么考虑每个数会被异或几次即可，设序列长度为 $n$，则位置 $i$ 上的数会被异或 $\binom {n-1}{i-1}$ 次。 这时候我们还要求出模 $2$ 意义下的组合数，一个简单的方法是计算每个阶乘的分解中 $2$ 的次数，将计算组合数时的除法改为做减法。则对于一个组合数，最后如果剩下的 $2$ 的次数为 $0$，则说明 $\bmod 2 = 1$，否则 $\bmod 2 = 0$。 对于阶乘的分解，可以先对每个数简单地求出分解中 $2$ 的次数，然后做前缀和即可。 时间复杂度 $\mathcal O(n)$。 ```cpp const int N = 1e6 + 7; int n, a[N], c[N]; char s[N]; int main() { rd(n), rds(s, n), --n; for (int i = 1; i <= n; i++) a[i] = abs(s[i] - s[i+1]); bool ok = 0; for (int i = 1; i <= n; i++) if (a[i] == 1) ok = 1; if (!ok) for (int i = 1; i <= n; i++) a[i] >>= 1; for (int i = 1; i <= n; i++) { int x = i; while (!(x & 1)) ++c[i], x >>= 1; c[i] += c[i-1]; } int ans = 0; for (int i = 1; i <= n; i++) ans ^= c[n-1] - c[i-1] - c[n-i] ? 0 : (a[i] & 1); if (!ok) ans <<= 1; print(ans); return 0; } ```