考虑当前数i,如果i是个奇数，那么他的分解数中有1，那么在i-1的所有可能分解后面都加上个1即可得到i的所有可能分解。 如果i是个偶数，那么分两种情况: 1.如果分解数中有1，那么在i-1的所有可能分解后面都加上个1即可得到这种情况下i的所有可能分解。 2.分解数中没有1，则每个分解数一定都是偶数，那么把i/2的所有可能分解的每个分解数都乘上2，即可得到这种情况下i的所有可能分解。
#include <cstdio>
#include <cstring>
#define mod 1000000000
#define N 1000005
int a[N],n;
int main(){
scanf(
"%d",&n);a[
1]=
1;
for(
int i=
2;i<=n;++i){
if(i&
1) a[i]=a[i-
1];
else a[i]=a[i-
1]+a[i>>
1];
a[i]%=mod;
}
printf(
"%d\n",a[n]);
return 0;
}
