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

然后呢？

$100\to 30$;

$1=\to3=$；

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

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

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），卡掉了如下的题解：

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$