[51nod1383&1048]整数分解为2的幂：DP

算法一

分析

\(f[x]=f[x-1]+f[x/2] \times [x \equiv 0 \mod 2],O(n)\)

代码

n=int(input())
f=[0]*(n+5)
f[0]=1
mod=1000000007
for i in range(1,n+1):
if i%2==0:
f[i]=(f[i-1]+f[i//2])%mod
else:
f[i]=f[i-1]
print(int(f[n]))
exit()

算法二

咕咕咕。