题解 [ARC066] B

皎月半洒花

2020-02-23 23:55:23

Solution

这个题有许多有趣的做法,这个地方说一种实现很简单但很有趣的做法。 考虑 $$ 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,就不放了。