ARC066B

ARC066B

给定 (N(1le Nle 10^{18}))，求 (u,vin [0,N]) 中有多少对 ((u,v)) 满足存在 (a,b) 满足 (aoplus b=u,a+b=v)

( m Sol:)

观察到 (v-u=(a& b) imes 2)，不妨对 (a&b(x)) 与 (aoplus b(u)) 进行计数。

考虑对 (a,b) 进行计数，假设当前位 (a,b) 均为 (0) 或为 (1)，那么对应的 (u,x) 位的数被唯一确定，否则为 ((0,1)) 则可以交换。

于是假设有 (m) 个 01，那么对答案的贡献为 (frac{1}{m})。（于是可以直接数位 dp 统计，复杂度 (mathcal O(log^2 n))）

观察到一组 (a,b) 对答案有贡献当且仅当 (a+ble n)，不难注意到交换 ((0,1)) 对的位置对 "和" 无影响，于是强制让 (a) 此位为 (0)，(b) 为 (1) 即可。

然后数位 dp 就是 (mathcal O(log n))

然而实际上可以直接算，设 (f_i) 表示满足 (a+ble i) 且合法的 ((a,b)) 组数量，然后直接从后往前填数，那么可以得到转移（当前填的数是最后一位）(f_i=f_{frac{i}{2}}+f_{frac{i-1}{2}}+f_{frac{i-2}{2}})