这道题一旦想开，其实思想十分简单的。
首先考虑n为奇数的情况，不难知f(n)=f(n-1)。（只需要把n的所有拆分式-1即可……）
然后考虑n为偶数的情况，将拆分式划分为两种情况：一种是式子中带1的，把1从式子中去掉就可以得到f(n-1)；一种是式子中不带1的，那么就把式子中的全部项除以2得到f(n/2)，则f(n)=f(n-1)+f(n/2)。
#include <stdio.h>
#include<stdlib.h>
#define DIV 1000000000
int num[1000001]={0};
int main()
{
int n,sum,i;
num[1]=1;
for(i=2;i<=1000000;i++)
{
if(i%2==1)
{
num[i]=num[i-1];
}
else
{
num[i]=num[i-1]+num[i/2];
}
num[i]%=DIV;
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",num[n]);
}
return 0;
}