很不错的一道题，这里提供两种方法：

方法1：递推；

易知当n为奇数时，f[n]=f[n-1] （n-1的所有方案前面添1，并且没有新的方案）；

重点是n为偶数的时候，则拆分方案中，要么有偶数个1，要么有没1；

当有偶数个1时，就相当于在n-1（奇数）的方案中添一个1，（每个奇数分解方案一定有奇数个1）；

当没1时，那么参加分解每个数都是偶数，所以方案数=f[n/2];

根据加法原理可知f[n]=f[n-1]+f[n/2];

 

方法2：这题也可以转化为完全背包来做：

因为只能用2^k来分解，且不考虑顺序：

容易想到就是k个物品，每个物品重量是2^k，来填满一个容积为n的背包；

所以，k=[logn]; 时间复杂度为O(nlogn); （完全背包问题见背包九讲）

虽然没有上一种方法时间复杂度优，但是体现了就看似是数学问题向背包问题转化的思路，（参见noip2012pj第三题）

1 const ff=1000000000; 2 var f:array[0..1000100] of int64; 3     d:array[0..50] of longint; 4     i,j,n,k:longint; 5 begin 6   readln(n); 7   k:=trunc(ln(n)/ln(2)); 8   d[0]:=1; 9   for i:=1 to k do10     d[i]:=d[i-1]*2;11   f[0]:=1;12   for i:=0 to k do13   begin14     for j:=d[i] to n do15     begin16       f[j]:=(f[j-d[i]]+f[j]);17       if f[j]>ff then f[j]:=f[j]-ff;18     end;19   end;20   writeln(f[n] mod ff);21 end.