题意要求求出给定整数分解为2的幂之和的方法数量。（貌似这题还有两个加强版orz日后填坑
写出前几项后可以观察出来规律：当n为奇数的时候 f(n)=f(n-1)，当n为偶数的时候f(n)=f(n/2)+f(n-2)。
这个规律的由来其实很简单，奇数的时候一定每一种分解都有至少一个1，说明这个1不是造成这些分法不同的原因，那么去掉他之后这些分法仍然是不同的，也就是数量没有减少，所以f(n)=f(n-1)。 而偶数的时候可以观察到分法可以分为两类，一类是有1的，这时候必定至少有两个1（因为n为偶数），换句话说这一类里面每种分法都有两个1，那么跟奇数那个同理这个也不是造成这些分法彼此不同的原因，所以去掉之后仍然是不同的也就是数量不会减少，这一部分相当于是f(n-2)； 另一部分都是2的倍数，那么把他们全部除以2的话也仍然保持不同也就是数量没有变，也就是说这一部分相当于f(n/2)。
一开始没写记忆化果断T了几发。。。
继续阅读“[暑期集训][数学][递推] 51nod 1383”