题解：P14636 [NOIP2025] 清仓甩卖 / sale
XZhuRen
·
·
题解
思路很简单的题，但是少了特判导致考场上调了很久，没时间写 T4 了，严厉谴责样例 4 强度太弱！
小 R 的顺序和最优策略顺序都是是将 $1,2$ 类物品降序排序后归并的结果，所以将 $a$ 降序排序，设 $a_{n+1}=0$。
我们求不合法方案数。
---
特殊性质：$m=2$，这时小 R 的策略非最优当且仅当存在 $B=1<A<C$ 满足 $w_A=w_C=1,w_B=2,a_A>\frac{a_{B}}{2}>a_c$，且 $a_c+a_a<a_b$，注意 $C$ 可以不存在，即 $C=n+1$。
则枚举 $A$，此时 $C$ 为一段后缀 $[C_l,n]$，贡献为 $2^{n-C_l+1}-[a_A=a_B]$，因为还有 $C$ 不存在，没写这个特判也能过 $\text{sale4}$。
---
推广到 $m\not=2$ 的情况。
这时 $A$ 是倒数第二/倒数第一个被购买的 $1$ 类物品，买 $A$ 后总钱数为 $m-1$。$B$ 是第一个没有被购买的 $2$ 类物品，改为枚举 $A,B$，右侧贡献不变。
考虑前面的贡献，此时要求求：前 $A-1$ 个物品，钦定了第 $B$ 个为二类，小 R 购买了 $B$ 之前的 $2$ 类物品及 $A$ 之前的 $1$ 类物品（不包括 $A,B$），求花费为 $m-2$ 的方案数 $f(A,B)$。
设 $c2$ 为前 $B-1$ 个的二类物品数，容易发现式子为：
$$f(A,B)=\sum_{c2=0}^{c2=B-1}\binom{B-1}{c2}\binom{A-B-1}{m-2-(B-1+c2)}$$
范德蒙德卷积得 $f(A,B)=\binom{A-2}{m-B-1}$。
左侧贡献和右侧贡献相乘即可。
代码等公示。