题目中涉及到了加法和异或，一个是进位加法，一个是不进位加法，显得很不可做。
但是我们注意到加法只加 \(1\)，如果产生进位了，那会将末尾的所有 \(1\) 推平成 \(0\)，而如果没有进位，则后面的位不会受到加法影响。
这启发我们挖掘这道题的过程。我们发现这个过程形似可以从低位推到高位，并且过程中会有很多整个后缀全部为 \(0\) 的状态。那么我们可以将过程分成若干个阶段阶段，并且发现，在 \([0,i-1]\) 位还未产生进位时，处理 \([i,40]\) 位的异或操作是简单的，只需要记录每个异或操作次数的奇偶性即可，因为他们不会收到加法影响，那么我们考虑 dp，设 \(f_{i,0/1,0/1,s}\) 表示考虑 \([0,i-1]\) 位，初始状态是 \(S\) 或全 \(0\)，末尾状态是 \(T\) 或进位，异或操作的奇偶性为 \(S\)，从初始状态到末尾状态的最小代价。
我们发现这个状态设计是足够的，现在考虑转移。
首先，第 \(i\) 位若可以直接匹配状态，直接转移就行，挨个讨论即可。
现在开始考虑需要多次进位的转移。首先，由于会出现进位，若我们要转移 \(f_{i+1,x,y,S}\)，首先我们显然要从 \(f_{i,x,1,S_0}\) 开始，然后，我们接下来将会进行一系列的异或和加法操作，在此过程中我们需控制进位只能在第 \(i\) 位进位，不能影响到最后的位置。最后，我们再以一个 \(f_{i,1,y,S_{m+1}}\) 的操作完成转移，\(m\) 表示中间的综合操作的次数，那么转移方程就呼之欲出了：
\[f_{i+1,x,y,\bigoplus_{j=0}^{m+1} S_j}=f_{i,x,1,S_0}+f_{i,1,y,S_{m+1}}+\sum_{j=1}^m f_{i,1,1,S_j} \]我们发现这个转移的形式其实是一个最短路形式，那么我们可以用 dijkstra 的方式去转移，最后答案为 \(\min(f_{40,0,0,S})\)，时间复杂度 \(\mathcal{O}(2^{2n}\log V)\)。
标签：XOR,我们,异或,AGC061E,Increment,加法,操作,转移,进位 From： https://www.cnblogs.com/lalaouyehome/p/18463863