AT5041 XOR Partitioning

注意到以下几点： 1. 对于所有段，它们的异或和就是所有数的异或和。 2. 由于所有段的异或和为一个定值，设它为 $d$，并设所有数的异或和为 $s$。设分成了 $x$ 段，则有 $s=[x\bmod 2 = 1]d$。 分类讨论。设 $A_{1\dots N}$ 的前缀异或和数组为 $s_{1\dots N}$。 若 $s\neq 0$，那么就表明 $d=s$，同时 $x$ 是奇数。考虑所有 $x$ 段的最后一个数的位置为 $p_{1\dots x}$，那么必定有 $s_{p_{i}}=[i\bmod 2=1]d$。因此问题转化为在 $s_{1\dots N}$ 中选择奇数个位置，且最后一个数必须选，满足奇数位置上的数为 $d$，偶数位置上的数为 $0$，求方案数。设 $f(i,0/1)$ 表示前 $i$ 个位置，选了 偶数 / 奇数 个位置时的方案数。转移： $$ f(i,0)=\begin{cases}f(i-1,0)&a_i\neq 0\\f(i-1,0)+f(i-1,1)&a_i=0\end{cases} $$ $$ f(i,1)=\begin{cases}f(i-1,1)&a_i\neq d\\f(i-1,1)+f(i-1,0)&a_i=d\end{cases} $$ 否则若 $s\neq 0$，那么就表明 $d$ 的值不一定确定，同时 $x$ 的奇偶性也未知。假设 $x$ 是奇数，这表明 $d=0$，做法同上。然后考虑 $x$ 是偶数的情况。 同上，问题为在 $s_{1\dots N}$ 中选择偶数个位置，结尾必须选，满足奇数位置上的数为 $d$，偶数位置上的数为 $0$。直接枚举 $d$ 复杂度显然是爆炸的。但是注意到上面的转移方程中，真正会产生转移的位置只有 $a_i=0$ 或 $a_i=d$ 两种。 因此预处理出 $a_i=d$ 的位置，然后对 $a_i=0$ 的位置进行一次前缀和，就可以快速转移了。 时间复杂度 $\mathcal O(N)$。