题解 CF1066E 【Binary Numbers AND Sum】

2018-10-20 14:11:52


模拟一下,可以发现 $a$ 不动, $b$ 每次向右移一位。

设最右边为第 $1$ 位,那么 $b$ 中的第 $i$ 位会经过 $a$ 中的 $1$ ~ $i$ 位。

比如:

 1001
10101

$b$ 的第三位会经过 $a$ 中 $1$ ~ $3$ 位,那么它对答案的贡献为 $2^0=1$ 。

再比如第五位,会经过 $a$ 中 $1$ ~ $4(\text{可以看作5})$ 位,那么它对答案的贡献为 $2^3+2^0=9$ 。

发现 $b$ 每一位的贡献是连续的,可以考虑前缀和。先将 $a$ 中的 $1$ 改成 $2$ 的幂,然后前缀和。

反着输入更好。

细节见代码