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

算法一

分析

(f[x]=f[x-1]+f[x/2] imes [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()

算法二

咕咕咕。