Poj 2229: Sumsets

poj2229.md

Poj 2229: Sumsets

題目

分析

完全沒想到啊…

觀察幾個例子：

2 = 1 + 1
  = 2

3 = 1 + 1 + 1
  = 1 + 2

4 = 1 + 1 + 1 + 1
  = 1 + 1 + 2
  = 2 + 2
  = 4

5 = 1 + 1 + 1 + 1 + 1
  = 1 + 1 + 1 + 2
  = 1 + 2 + 2
  = 1 + 4

---

藉由 奇數偶數 分開處理，可得到下面想法

Let dp[i] = the number of ways to represent N

---

奇數就是前一個偶數，每種方法都加上一個 1，所以

dp[i] = dp[i-1]

---

偶數的話分兩個部分：那些 含有 1 的表示法 跟 其它沒有的，例如 4 就是

4 = 1 + 1 + 1 + 1
  = 1 + 1 + 2

和

4 = 2 + 2
  = 4

前一個部分就是 3 的每種方法再加 1；後一個部分是 2 的每種方法都乘 2，所以式子寫成：

dp[i] = dp[i-1] + dp[i/2]

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int N;
long long dp[1000000 + 1];

int solve() {
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (i & 1)
            dp[i] = dp[i-1];
        else
            dp[i] = dp[i-1] + dp[i / 2];
        dp[i] = dp[i] % 1000000000;
    }

    return dp[N];
}

int main() {
    scanf("%d", &N);
    printf("%d\n", solve());
    return 0;
}