Sumsets

数学递推。

看完题面第一时间的想法就是O(NlgN)地枚举。。。竟然过了。然后看了下status，有0ms的，便开始想数学解法。。。

没什么思路后，开始观察规律：将2、4、8、16、32打表出来，没发现什么规律。就把1到32的全打出来了，发现两数之间的计数值间的差值有点像等差数列，又猜了一下便发现递推公式是：
f(x)=1, x=0
f(x)=x-1, x%2==1
f(x)=f(x/2)+f(x-2), else

但AC了之后依然不知道为什么式子是这样的。。。又经过漫长的分析之后发现，可以将x的表示方式分为两类（这里x为偶数，奇数情况容易发现即为x-1的计数值）：
（1）合式中含有1的：这种情况x的表示形式和x/2是相同的，其中x合式中的2便对应着x/2合式中的1，依次类推；
（2）合式中不含1：这里x的合式中至少要有2个1（因为x是偶数），因此其表示形式可以由x-2的形式+1+1得到；

以上两类刚好能不重复地包含x的全部表示形式，因此便能得到前面的公式了。