题解：P14636 [NOIP2025] 清仓甩卖 / sale

退役喽！考场上被控三小时才做出来，但是思维并不难，至少我的做法是蓝题水平。

特殊性质非常良心啊，从特殊性质开始想。先按照原价从小到大排序。考虑 $m=2$ 的情况，如果是个非法状态，那么必然是有一个代价为 $1$ 的在第一位，一个代价为 $2$ 的在第二位，且在第二位往后还有一个代价为 $1$ 的。我们计这三个原价分别为 $x,y,z$，那么非法状态条件即为 $x+y<z$，因为此时由于考虑到 $y$ 的时候钱只剩 $1$ 了，将会购买 $x+z$。

还注意到这个代价为 $2$ 的肯定是原价最大的，枚举第一个代价为 $1$ 的，利用二分或双指针找到下一个代价为 $1$ 的可能的范围便可轻松计算，这个范围的左端点肯定是 $1$，右端点记为 $pos$，答案为 $2^{pos}$。最后将所有状态减去非法状态即可。

考虑正解，枚举上式的 $y$ 和 $x$ 的位置，分别计为 $i,j$，那么参考下图（虽然很丑）：

横线上方是下标，下方是值的位置。

还是计算非法状态，显然我们 $j$ 的取值是粉色这一段，即 $\frac{a_i}{2}< a_j < a_i$，显然红色这一段最后会在 $i$ 的前面被购买，绿色这一段如果价格取 $1$ 的话也会在 $i$ 前面被购买，最后一个 $1$ 的位置会在蓝色这一段，这一段中随便取，与特殊性质相同。考虑 $i$ 前面的取值方案。

由于 $j$ 这个点我们一定要取到 $1$，考虑到 $i$ 的时候需要剩下 $1$ 元钱，那么绿色+红色这一段的需要消耗的钱数为 $m-2$。

红色这一段每个数要么是 $1$ 要么是 $2$，绿色这一段要么是 $0$ 要么是 $1$。朴素想法是枚举每一段用了多少，但是这样时间会爆，其实本质上这两段没有很大的区别，我们将红色的这一段全都提出来一个 $1$，这样红色绿色两段我们就能合并为一段，再用组合数计算即可得到前面的方案数，和后面的蓝色方案数乘法原理处理即可。

考场上做法过了大样例，但是由于退役了代码就咕咕了，等发代码之后可能会补上吧。