poj 2229 Sumsets

#include <cstdio>
#include <string.h>

int sum;
int d[1000001];

int main() {
  scanf("%d", &sum);
  int i;
  // 初始化唯一确定方案数，d[1] 为 1 表示 1 的分解方案只有 1 种
  d[1] = 1;
  for(i=2;i<=sum;++i) {
    // 找规律，当 i 为偶数的时候方案数为 i / 2 的方案数再加上 i-1的方案数
    // 当 i 为偶数时才体现出 2 的幂之和，因为除了加 1 之外其余加的都是为偶数的2的n次幂，这个是重要的入手点
    if ((i & 0x1) == 0) {
      d[i] = d[i/2];
    }
    // 不论奇偶都要加上他们前一个数的方案数
    d[i] += d[i-1];
    // WA 的时候仔细再看题目才发现要取一下模
    d[i] %= 1000000000;
  }

  printf("%d\n", d[sum]);

  return 0;
}