「PR #14」安顿

考虑要求划分数量最多，假如所有数都不等于 \(X\) 那么一个一个划显然最好，有 \(X\) 的话 \(X\) 所在段必须有至少两个元素，再继续讨论。当 \(X=0\) 时，显然将其划分到旁边的一个段内，所以其答案就是非 \(0\) 的元素数量。但是我们还没有清楚为什么要把这种情况单独拿出来。这种做法不能解决 \(X≠0\) 的原因在于，两个 \(X\) 可以变成合法的，并且 \(X\) 和一个非 \(X\) 元素分在一组仍异或结果仍可能是 \(X\)。但是这种情况下我们似乎是考虑贪心，直接对于只包含 \(X\) 与 \(0\) 的极长连续段来看，它们如果要接到段外面，必然只和靠边那一个元素分在一组即可，而这些都与 \(X\) 的具体值无关。由此我们可以断言，\(X≠0\) 的情况答案都是一样的！

那就考察 \(X=1\)。或许你会问，为什么偏偏是这一个？从刚才的做法来看，这与 \(X\) 是多少确乎无关？但是我们可以对此考虑另外一个做法。我们考虑长度为 \(n+1\) 的前缀异或序列（这显然也是等概率的），那么显然问题是选出其中若干个数，相邻两个的异或不为 \(1\)，并且首和尾必选。把每个数写成 \(2A+B\) 的形式，其中 \(0\le B \le 1\)，那么我们只需要考虑 \(A\) 相同的连续段就可以了。每个连续段内肯定选 \(B\) 的两种值出现次数更多那个就行了。

这样就可以考虑计数了。我们考虑枚举连续段长度 \(L\)，枚举这个连续段的 \(A\)，那么只需要分情况讨论（为了方便计数，钦定第一个数可以任意而不是 \(0\)，不难发现这样期望是不变的）：

• 它是中间段。钦定旁边两个数的 \(A\) 与其不同，段外的其它数随便选。再枚举段内 \(B=0\) 的个数 \(i\)，则还没确定的数产生的总贡献就是 \(\sum\limits_{i=0}^L \max\{i,L-i\}\dbinom{L}{i}\)，这个式子拆成两半，最后是可以 \(\mathcal O(1)\) 算的。

• 它是边缘段。钦定的东西还是差不多。只不过要钦定位于序列末端/尾端的必须选。还是列式子，化简。

• 它是整个序列。因为这个涉及到判断有无解的问题。容易发现，当序列首尾异或为 \(1\) 并且整个序列位于一个段时无解。否则钦定首尾必选，其他还是差不多。

以上三部分都是可以 \(\mathcal O(1)\) 算的，所以最终复杂度是 \(\mathcal O(n)\) 的，至此本题就做完了。可以发现上面这个东西在 \(X>1\) 时也可以尝试，只不过 \(B\) 的值域更大，判定条件更加答辩。这就是本题的妙处：通过一种贪心（或者是感性理解）得到 \(X≠0\) 的情况答案相等的结论，又通过一个截然不同，并且看似不满足看出（或者说看不出满足）上面的结论的一个贪心，完成 \(X=1\) 的计数，来通过此题。