题解 [ARC066] B

· · 题解

这个题有许多有趣的做法，这个地方说一种实现很简单但很有趣的做法。

考虑

a+b=((a~\mathrm{and}~b)<<1)+(a~\mathrm{xor}~b)

这个式子的意义在于，后半部分是因为异或运算是二进制下不进位的加法，前半部分则是在描述二进制下的进位。反正无论怎么样，我们可以轻松得到 a+b\geq a~\mathrm{xor}~b 这样的结论。

那么如果由于 u\leq v，所以如果 v 不越界那么 u 一定不越界。于是考虑按 v 进行 dp。具体的，考虑状态 f_{i,j} 表示考虑了 a 和 b 二进制下的前 i 位，当前 v=a+b=j 的方案数。

考虑如何转移。对于 a 和 b 而言，第 i 位有三种情况，(0,0),(0,1),(1,1) 。那么也就是假设原来的和为 j'，和当前的和 j 可能有以下关系：

1、2\cdot (j'+1)=j，对应着都补一位 1。

2、2\cdot j'=j，对应着都补一位 0 。

3、j'+ (j' + 1)=j，对应着一个补 1 一个补 0 。

那么也就是

f_{i,j}=f_{i-1,\lfloor\frac{j}{2}\rfloor}+f_{i-1,\lfloor\frac{(j-1)}{2}\rfloor}+f_{i-1,\lfloor\frac{(j-2)}{2}\rfloor}

发现本质上，第一维状态随着第二维递减，且都是 \Delta(\log) 级别，并且每次计算，必定存在三项中有两项是相等的，所以可知最后状态数一定介于 \Omega(2\log N)\sim O(\log N) 之间，可以通过本题。

考虑把第一维压掉之后，就是另一篇题解的那种做法了。

代码实现十分naive，就不放了。