BZOJ 1677 [Usaco2005 Jan]Sumsets 求和

发布于 2017-04-08  162 次阅读


题意:给出一个 N(1N10^6),使用一些 2 的若干次幂的数相加来求之.问有多少种方法

式子是显然的:

当 i 为奇数,f[i]=f[i-1]
当 i 为偶数,f[i]=f[i-1]+f[i>>1]

证明如下:

奇数时,分解的方式中一定有一个 1,那么去掉这个 1 即为 f[i-1] 的情况。

偶数时,分为含有 1 和不含有 1 两种情况。

若含有 1,则直接去掉这个 1。若不含有 1,即分解方案中均为偶数,将方案中的每一个数除二即与 f[i>>1] 的方案一一对应。

代码:

 


一个非常弱的准退役OIER