AGC061E. Increment or Xor
前情提要：[ULR #2] Picks loves segment tree IX, [CF1007E] Mini Metro。读者容易感受到这两题与此题的联系。
核心问题是阶段的划分。但是以上两题的任意一题都已经提示我们：以前若干位为阶段，直到第一次向上进位或是主动固定前若干位再继续。因为进位会使得前若干位都清零。
上面这句话可能比较抽象，我们直接抛出状态：\(f(k, s, t, p)\)，表示当前聚焦 \(0, \dots, k-1\) 位，初始是全 \(0\) 或 \(S\)（分别用 \(s=0,1\) 标记），最后是全 \(0\) 且向上进位或 \(T\)（分别用 \(t=1,0\) 标记），过程中使用的 \(Y_i\) 的奇偶性为 \(p\)，且过程中不能向上进位，除非 \(t=0\)。
那么要么我们中间（不包括最后一次）进行了 \(0\) 次进位就开始考虑第 \(k\) 位，即直接转移到 \(f(k+1, \dots)\)（需要状态匹配）；要么是中间进行了 \(\ge 1\) 次进位才开始考虑第 \(k\) 位，需要从 \(f(k, s, 1, p_0) + f(k, 0, 1, p_1) + f(k, 0, 1, p_2) + \dots + f(k, 0, t, p_m)\) 转移到 \(f\left(k+1, s, t, \bigoplus_{i=1}^m p_i\right)\)。这是一个最短路的形式，Dijkstra 即可。
\(+1\) 操作我们在初值体现就行了。
时间复杂度 \(O(4^N \log V)\)。