笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 [ARC066] B

posted on 2020-02-23 23:55:23 | under 题解 |

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

考虑

$$ 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,就不放了。