Algoogle

Algorithm for Programming Contest

PKU 2229 Sumsets

Category: PKU Tag: dp

Sumsets

問題概要


解法


各数は今までに使った値の最大以上の値をうしろにくっつけることで作れる.
つまり 1 + 2 で 3 が作られるとき, 2, 4, 8 … が足すことができる.
よって各数のうしろに 1 を足す場合の数, 2を足す場合の数 … と求めることができる.

1
2
3
for i in 1, 2, 4, 8 ...
    for j in i+0, i+1, i+2, i+3 ...
        dp[i+j] += dp[j]

となるので O(N log N) で間に合う. #code1

が O(N) 解法が存在した. #code2
ある数 i を作るには i-1 に 1 を足すのと i/2 を2倍するかだけですべての場合をカバーできる.
サンプルの場合は6の場合に1を足すだけで表現できる. (奇数は偶数+1でしか表せない)
6 は 5+1 か 3 * 2 で表現されていることがわかる.

コード


#code1

(2229.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>

using namespace std;

const int mod = int(1e9);
int N;
int dp[1000010];

int main(){
    scanf("%d", &N);
    dp[0] = 1;
    for(int i = 1; i <= N; i <<= 1)
        for(int j = 0; j + i <= N; j++)
            dp[i+j] = (dp[i+j] + dp[j]) % mod;
    printf("%d\n", dp[N]);
    return 0;
}

#code2

(2229_2.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>

using namespace std;

const int mod = int(1e9);
int N;
int dp[1000010];

int main(){
    scanf("%d", &N);
    dp[0] = 1;
    for(int i = 1; i <= N; i++){
        if(i % 2 == 0) dp[i] += dp[i / 2];
        dp[i] += dp[i-1];
        dp[i] %= mod;
    }
    printf("%d\n", dp[N]);
    return 0;
}

Comments