BZOJ 1677 [Usaco2005 Jan]Sumsets 求和


题意:给出一个 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] 的方案一一对应。

代码:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1677 [Usaco2005 Jan]Sumsets 求和


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: