poj 2229 Sumsets

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;#define maxn 1000006int ans[maxn];int main(){    int n;    scanf("%d", &n);    ans[1] =1;    for (int i =2; i <= n; i++)    {        if (i &1) ans[i] = ans[i -1];        else ans[i] = ans[i -1] + ans[i /2];        ans[i] = ans[i] %1000000000;    }    printf("%dn", ans[n]);    return 0;}