AGC061E. Increment or Xor 2024-07-01 20:25 folder 题解

前情提要：[ULR #2] Picks loves segment tree IX, [CF1007E] Mini Metro。读者容易感受到这两题与此题的联系。

核心问题是阶段的划分。但是以上两题的任意一题都已经提示我们：以前若干位为阶段，直到第一次向上进位或是主动固定前若干位再继续。因为进位会使得前若干位都清零。

上面这句话可能比较抽象，我们直接抛出状态：f(k,s,t,p)，表示当前聚焦 0,…,k−1 位，初始是全 0 或 S（分别用 s=0,1 标记），最后是全 0 且向上进位或 T（分别用 t=1,0 标记），过程中使用的 Yi 的奇偶性为 p，且过程中不能向上进位，除非 t=0。

那么要么我们中间（不包括最后一次）进行了 0 次进位就开始考虑第 k 位，即直接转移到 f(k+1,…)（需要状态匹配）；要么是中间进行了 ≥1 次进位才开始考虑第 k 位，需要从 f(k,s,1,p0)+f(k,0,1,p1)+f(k,0,1,p2)+⋯+f(k,0,t,pm) 转移到 f(k+1,s,t,⨁mi=1pi)。这是一个最短路的形式，Dijkstra 即可。

+1 操作我们在初值体现就行了。

时间复杂度 O(4NlogV)。