整数拆分

题目描述

一个整数总可以拆分为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。

输入：

每组输入包含一个整数：N（1<=N<=1000000）。

输出：

对于每组数据，输出f（n）％1000000000。

样例输入：

7

样例输出：

6

分析

对于奇数n=2k+1：它的拆分的第一项必然是1，推敲去掉这个1，其实就一一对应于
2k的拆分，是以f（2k+1）=f（2k）.

对于偶数n=2k：推敲有1和没有1的拆分。有1的拆分，与（2k-1）的拆分一一对应，与上方奇数的景象
来由雷同；没有1的拆分，将每项除以2，正好一一对应于k的所有拆分。是以f（2k）=f（2k-1）+f（k）.

须要重视f（n）会很大，不要溢出了。终极成果只请求除以十亿的余数，在int的默示局限内，
是以不须要大数运算。重视余数的性质：（a+b）％m == （a％m+b％m）％m，所以只要对每个中心
成果也都取余数，就不会有溢出的题目，且不改变终极输出成果。

#include <stdio.h>
int f[1000001];
int main()
{
    int i,n;
    while(scanf("%d",&n)!=EOF)
    {
        f[0]=1;
        f[1]=1;
        for(i=2;i<=n;i++)
        {
            if(i%2==0)
                f[i]=(f[i-1]+f[i/2])%1000000000;
            else
                f[i]=f[i-1];
        }
        printf("%d\n",f[n]);
    }
}