【模板】背包方案计数（弱化版）

2018 年 1 月 21 日，某同学在洛谷P1164 小A点菜里面使用了一个广为人知的算法求方案数。

然后呢？

100\to 30

;

1=\to3=

；

最终，他因此没能与理想的大学达成契约。

yummy 衷心祝愿大家不再重蹈覆辙。

CPP

36 32
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 8 16

yummy构造了如上的数据（答案2147483647），卡掉了如下的题解：

CPP

https://www.luogu.com.cn/blog/stoorz/solution-p1164
https://www.luogu.com.cn/blog/yby39/solution-p1164
https://www.luogu.com.cn/blog/user38036/solution-p1164
https://www.luogu.com.cn/blog/RichardWilliams/solution-p1164
https://www.luogu.com.cn/blog/37539/solution-p1164
https://www.luogu.com.cn/blog/bill07/solution-p1164
https://www.luogu.com.cn/blog/ArthasMenethil/solution-p1164
https://www.luogu.com.cn/blog/KLOVE/solution-p1164 （这篇只要时间对比修改下就好）
https://www.luogu.com.cn/blog/mxxr/solution-p1164
https://www.luogu.com.cn/blog/user21390/solution-p1164（这篇不太确定，因为貌似记忆化了，但是我看不懂）
https://www.luogu.com.cn/blog/RedContritio/solution-p1164
https://www.luogu.com.cn/blog/iiii32/solution-p1164
https://www.luogu.com.cn/blog/wawcac/solution-p1164

讲一讲我怎么Hack的：

上面这些题解的复杂度都是

O(方案数)

的，但是由于int只有

2^{31}-1

的范围，如果数据不好，常数小一点可能真能过。

为了达成该目的，需要尽量最大化方案数，还不能超过上限，于是我将数据拆成两部分，第一部分有

31

个1，第二部分是

1,2,4,8,16

，每一个第一部分的取和不取（非空除外），都能对应第二部分的一个取和不取。

我们可以通过数学论证得到答案为

C_{31}^1+C_{31}^2+\ldots+C_{31}^{31}=2^{31}-1

【模板】背包方案计数（弱化版）

讨论操作

回复

相关推荐

【模板】背包方案计数（弱化版）