02229: Sumsets

http://cs101.openjudge.cn/practice/02229/

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1)1+1+1+1+1+1+1

2)1+1+1+1+1+2

3)1+1+1+2+2

4)1+1+1+4

5)1+2+2+2

6)1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

输入

A single line with a single integer, N.

输出

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

样例输入

样例输出

来源

USACO 2005 January Silver

python

# 按照整数划分来做
'''
递推式：
如果i为奇数：那么它一定可以由f[i-1]转移过来，是前面的那个数所有方案里都加了一个1

如果i为偶数：它可以看成是f[i-2]中的方案加了一个2，或者是f[i/2]的方案里乘了一个2；
所以应该是f[i-2]和f[i/2]的和

'''
MOD = 10**9
N = int(input())
dp = [1] + [0]*N
for i in range(1, N+1):
    if i & 1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-2] + dp[i//2]) % MOD # 

print(dp[-1])

python

# 完全背包来做，还要保证幂次方有序

import math

N = int(input())
ln = int(math.log2(N))
dp = [1] + [0]*N
MOD = 10**9
items = []
for i in range(ln+1):
    items.append(pow(2, i))
    
for i in items:
    for j in range(i, N+1):
        dp[j] = (dp[j] + dp[j-i]) % MOD

print(dp[-1])

02229: Sumsets ​

02229: Sumsets