POJ 2229 Sumsets

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

int sum;
int d[1000001];

int main() {
  scanf("%d", &sum);
  int i;
  // Initialize the unique solution count, d[1] = 1 means there is only 1 way to decompose 1
  d[1] = 1;
  for(i=2;i<=sum;++i) {
    // Find the pattern: when i is even, the number of solutions equals the number of solutions for i/2 plus the number of solutions for i-1
    // When i is even, it reflects the sum of powers of 2, because except for adding 1, all other additions are even powers of 2 (2^n), which is an important starting point
    if ((i & 0x1) == 0) {
      d[i] = d[i/2];
    }
    // Regardless of odd or even, add the solution count of the previous number
    d[i] += d[i-1];
    // When getting WA, look at the problem carefully again and realize we need to take modulo
    d[i] %= 1000000000;
  }

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

  return 0;
}