ROX

不难想到找规律，旁边的 DP。

666，这题是找规律我直接 AFO。找规律不是找关于通项公式的吗？我这个函数是递推的，我找什么？？？？瞪出递推公式吗？？？？

显然，你用线性的复杂度打出表，发现没有任何的规律。至少你瞪不出来（菜就多练）。

所以，这种神秘题目应当考虑 DP.

观察可得，我们给他二进制拆分一波，发现每一位似乎是独立的。

于是，我们从高向低地推。

令现在考虑的数字为 $k$。

$(k)_2 = (\cdots 0)$，如果原数字二进制表示是左边形式，也就是偶数，不难发现 $2^0$ 不做贡献，答案就是 $2f(k/2)+2f(k/2-1)$，因为右移一位后，答案要乘 $2$， $k/2$ 对应另一个数是偶数，反过来就是奇数。

反之，$(k)_2 = (\dots 1)$，如果原数字是奇数，无论另一个数字的取值，都有 $2^0$ 的贡献。一共有 $2 \times (k / 2 + 1)$ 个，另一个数出去末位，他的取值是 $k/2 + 1$ （有 $0$），再乘上 $2$，因为末位可 $1$ 可 $0$。然而，前面的数位还有 $4f(k/2)$ 的贡献。因为先乘 $2$ ，保证位数对齐。再乘 $2$ 因为末位可 $1$ 可 $0$。

具体的方程直接看 WZH 的。

最后 DP 即可，有高精度。