poj 2229 Sumsets

 1 #include <cstdio>
 2 #include <cstring>
 3 int n;
 4 #define M 1000000000
 5 int dp[1000002];
 6 
 7 int main(int argc, char const *argv[])
 8 {
 9     dp[1] = 1;
10     dp[2] = 2;
11     for(int i = 3; i <= 1000000; i++) {
12         if(i&1) {
13             dp[i] = dp[i-1];
14         }
15         else {
16             dp[i] = (dp[i-1] + dp[i>>1]) % M;
17         }
18     }
19     scanf("%d",&n);
20     printf("%d\n",dp[n]);
21     
22     return 0;
23 }