[题解] Ptz Camp Summer 2022 Day3 K. Kitten's computer

· · 个人记录

nb 题（

下文中 w 为值域，即 2^{64}

一个朴素的想法是不断让 x+y 变成 (x\operatorname{xor}y)+2(x\operatorname{and} y)，直到 x\operatorname{and} y=0 为止

但这样所需要的时间是 \mathcal O(\log w) 的，需要优化

考虑先把 (x,y) 变为 (x\operatorname{xor}y,x\operatorname{and} y)，然后考虑后者对前者的贡献（即进位的贡献）

记 f=x\operatorname{xor}y,g=x\operatorname{and}y，f_i 为 f 的第 i 位，g_i 同理

那么 g 对 f 第 i 位的贡献即为 \operatorname{xor}_{j<i}(g_j\operatorname {and}(\operatorname{and}_{j<k<i}f_i))（正确性由 f\operatorname{and} g=0 保证）

考虑用倍增优化这个操作，第 i 轮中令 (f_k,g_k)\leftarrow (f_k\operatorname{and}f_{k-2^i},g_k\operatorname{xor}(g_{k-2^i}f_k))

这样计算两个数相加的总时间为 $2\log\log w+2=14$，可以接受 + part 2：乘法器 要计算 $x\times y$，考虑先把 $y$ 拆位，然后变成 $\log w$ 个数连加 提取出 $y$ 的第 $i$ 位可以先左移 $63-i$ 位再右移 $63$ 位，另外我们需要实现一个计算 $x\times 0/1$ 的操作，可以直接倍增地把拆出来的位扩成 `1111..1` 或 `0000..0` 的形式，之后直接求与即可 拆位的时间开销 $2\log\log w+3=15

接下来我们只需要处理 \log w 个数连加，但直接用加法器显然不可以

考虑到 x+y+z=(x\operatorname{xor}y\operatorname{xor}z)+2((x\operatorname{and}y)\operatorname{xor}(y\operatorname{and}z)\operatorname{xor}(z\operatorname{and}x))，于是我们可以花费 4 的时间把三个数相加变成两个数相加

不断操作下去，可以把问题转化为两个数相加，这部分时间开销为 4\log_{1.5}\log w\approx 41

最后两个数相加可以直接用加法器解决，总时间开销可以在 70 以内，实测时间开销为 65