本题部分分可用于找规律。

Solution 1

在OEIS中输入任意前几个数，发现这个数列可以在这篇文章中找到：

https://oeis.org/A000695/a000695_1.pdf

翻到Corollary 3，发现它的递归式是

$$T(2^k+i)=\begin{cases} \frac13(2^{2k+1}+1)&\text{if }i=0;\\ T(2^k)+2T(i)+T(i+1)-1&\text{if }i=1,\dots,2^k-1.\\ \end{cases} $$

关于递归式的详细推导可参考文章。

照着写即可。注意需要使用记忆化和unordered_map。

时间复杂度$O(有点难算)$，期望得分100。如果使用map期望得分可能是70。