poj2229 Sumsets

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int dp[1000005];
 5 int main()
 6 {
 7     long long n;
 8     scanf("%lld",&n);
 9     dp[0]=0;
10     dp[1]=1;
11     dp[2]=2;
12     for(int i=3;i<=n;i++)
13         if(i%2==0)
14             dp[i]=(dp[i-2]+dp[i/2])%1000000000;
15         else
16             dp[i]=dp[i-1];
17     cout<<dp[n]%1000000000<<endl;
18     return 0;
19 }