PKU 2229 Sumsets

http://poj.org/problem?id=2229
ある数を2の累乗で表される数字の和で表す時、何通りの表し方があるかを答えるというような問題。

やたらと正解者数が多いのに、開くたびに気づけなくて諦めかけていた問題。
最初は使う数字が一番小さい物を覚えておくdpだと思ったのですが、よく考えるとそれだと計算量が少し大きくなりすぎてしまいそうだったので、考え直しました。
ただ、ある数Nが2の累乗で表せるとき、その数-1の表し方に+1する方法と、もう一つはその数/2の表し方を全て*2する方法があるということに気づいたので、それでdpしたら通りました。

もやもやが一つすっきりしました。

ll dp[1000001];

main(){
  dp[1]=1;
  for(int i=2;i<=1000000;++i){
    if(i%2==0)
      dp[i]+=dp[i/2];

    dp[i]+=dp[i-1];
    dp[i]%=1000000000;
  }
  int n;
  while(cin>>n)cout<<dp[n]<<endl;
}