Description

一个整数总可以拆分为2的幂的和，例如：
7=1+2+4
7=1+2+2+2
7=1+1+1+4
7=1+1+1+2+2
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
总共有六种不同的拆分方式。
再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。
用f(n)表示n的不同拆分的种数，例如f(7)=6.
要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

Input

每组输入包括一个整数：N(1<=N<=1000000)。

Output

对于每组数据，输出f(n)%1000000000。

Sample Input

7

Sample Output

6

在刚拿到这道题的时候我是一筹莫展的，但是自己代入几个数推几遍之后，就发现了规律，而发现规律的过程中也借鉴了网络，网上大部分的思路也是这样的：像这样拆分整数时，拆出的式子对于奇数(2k+1)来说第一项总是1，减去这个1就是偶数(2k)的拆分,所以f(2k+1)=f(2k)；而对于偶数，又有第一项是1的和第一项不是1的，对于第一项是1的部分，我们发现它的第二项也是1，也就是说减去这个1对拆分个数也没影响，即f(2k)[第一项是1]=f(2k-1)=f(2k-2)；而对于第一项不是1的部分，我们发现把每一项都除以2与这个偶数的一半那个数的拆分一一对应，即f(2k)[第一项不是1]=f(k)。

由此我们看到每一个数的拆分都可以由前面的拆分推出来，但有对应关系数与数之间跨度比较大，所以需要用一个数组把它们每一项在递推的过程中都记下来才能维持递推的过程。

具体代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

int f[1000010];

int main()
{
    int n;
    f[0] = 1;
    f[1] = 1;//对于0和1，它们只有一种拆分，由此开始递推。
    while(cin >> n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(i % 2) f[i] = f[i-1];
            else
            {
                f[i] = (f[i-1] + f[i/2]) % 1000000000;
            }
        }
        cout << f[n] << endl;
    }
    return 0;
}