显然$f(1)=1$。设n的二进制表示是$b_kb_{k-1}\ldots b_0$。
若$n$是偶数，则$b_0=0$，此时有两种情形：
1) 将某个为1的$b_j$ (即展开式中的$2^j$项)拆成两个$2^{j-1}$或若干更低的幂之和，但保持$b_0=0$不变，则拆法和分拆$b_kb_{k-1}\ldots b_1$的方式相同，即等于$f(n/2)$。
2) 将某个为1的$b_j$ (即展开式中的$2^j$项)拆成两个$2^{j-1}$或若干更低的幂之和，但拆分后需要有$2^0=1$这一项，由于n是偶数，因此拆分后必然有两个1， 除去这两个1后拆法的计算与1）中类似，因此共有$f((n-2)/2)$种方式。
若n是奇数，则$b_0=1$因而无法将其它项拆分到1（否则将有至少三个1不合题意），因此按上述分式分析可知共有$f((n-1)/2)$种方法。
综上可得
$$f(n)=\begin{cases}1 & n\le 1 \\ f(\frac{n-1}{2}) & n \text{为奇数}, \\ f(\frac{n}{2})+f(\frac{n-2}{2}) & n \text{为偶数}.\end{cases}$$
递推计算即可得结果$178653872807$。
注：以下为Python3代码，因记忆化搜索（cache装饰器）是Python3新增的功能。
from functools import *
@cache
def f(n):
if n<=1:
return 1
elif n%2==1:
return f((n-1)//2)
else:
return f(n//2)+f((n-2)//2)
print(f(10**25))
|
