已完成xor与+1运算大学习

· · 个人记录

门

考虑每次+1的作用：把低位到高位的一段1变成0 那么对于这个前缀，就有三种情况，并且变化是形如 1->(2)->3 的：

  1. 整个前缀是S的前缀
  2. 刚成为进位的牺牲品，全是0
  3. 整个前缀搞成T的前缀了

考虑每个前缀的初态与末态：

  1. 初态：情况1,2
  2. 末态：情况2(0结束，进1位),3(钦定不动)

同时，在他没有因为进位归0时，我们只要知道每个Y_i用了几次就可以确定目前状态。

据此，记录dp_{i,j0,j1,st} 表示考虑0 \sim i-1 位的前缀从j0的初态->j1的末态，当前st用了奇数次

考虑对第i位的转移：

  1. 如果直接可以转移，就直接转移，式子显然。
  2. 如果进行了进位：整个的状态(2为上文的0情况）就是j0->2->2->...->j1的状态，条件是不能上到i+1位。

每个2都代表了在当前位上的一次进位，在任意一位上，都有可能进位多次，所以有多次0，代表异或了一次st'又进了一次位。
然后发现这是类最短路形式，跑个dij转移就行了。