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

2024-09-05 18:55:05

算法一

分析

\(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()

算法二

咕咕咕。

最新文章

热门文章