“完全背包问题”

相当于不限量的体积分别为1, 2, 4, 8, …的物品.

时间复杂度

O(n*log(n))

Python 代码

MOD = 10 ** 9
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
i = 1
while i <= n:
    for j in range(i, n + 1):
        dp[j] = (dp[j] + dp[j - i]) % MOD
    i <<= 1
print(dp[n])