接下来，我们深呼吸，进入 T2 清仓甩卖 (Clearance Sale)。这道题的难度会有明显的跃升。

【T2 题目简化回顾】 小 X 的糖果店剩下 $n$ 颗糖，第 $i$ 颗糖的原价是 $a_i$。 现在小 X 搞清仓甩卖，每颗糖的清仓价只能定为 1 元 或者 2 元。 小 R 带了 $m$ 元来买糖，他的策略非常“死板”：

1. 他会计算每颗糖的性价比 = 原价 / 清仓价。
2. 他把所有糖按性价比从大到小排序（如果性价比一样，原价大的优先；还一样就编号小的优先）。
3. 他从头到尾按这个顺序看，如果手里的钱够买当前的糖，就买；不够就跳过，看下一颗。

目标： 在所有 $2^n$ 种定价方案（每颗糖定 1 或 2）中，有多少种方案能让小 R 这种“死板的贪心策略”买到的糖果原价总和，恰好等于理论上的最大可能原价总和（也就是小 R 没有被坑，真的买到了最优解）？ （答案对 998244353 取模）

---

教练的引导提问（第一步）：

正难则反。求“满足要求”的方案数很难，我们不妨先来看看，小 R 这个死板的贪心策略，在什么情况下会“翻车”（也就是没买到最大原价总和）？

我们来做一个小测试。假设小 R 手里有 $m=2$ 元钱。 这里有两颗糖：

• 糖 A：原价 6 元，清仓价被定为 1 元。
• 糖 B：原价 10 元，清仓价被定为 2 元。

请你代入小 R 的大脑，按他的“死板策略”（算性价比 -> 排序 -> 贪心买），他会买到哪颗糖？剩下的钱还够干嘛？他买到的原价总和是多少？ 但是，如果是“上帝视角”求最大原价总和，我们本来应该怎么买？两者差了多少？

（仔细算算这个小例子，这是解开这道题的最关键的一把钥匙！）

小R先买性价比最高的A，然后买不了B了，原价总和=6. 但是最优应该是买B，原价总和=10。 差了4。

完全正确！你不仅算对了，而且一眼看透了小 R 贪心策略的致命弱点——“为了追求高性价比，反而丢了总价值大的物品”。

在刚才的例子中，糖 A 就像是“诱饵”，它的性价比高达 6，吸引小 R 优先把钱花在它身上；但实际上，性价比稍微低一点（为 5）的糖 B，才是真正的大头！小 R 买了 A 之后兜里只剩 1 块钱，遇到 B 时就只能干瞪眼了。

我们把你的发现抽象成数学公式。假设有两颗糖：

• 糖 $i$（也就是前面的 A）：被定为 1 元，原价是 $a_i$。
• 糖 $j$（也就是前面的 B）：被定为 2 元，原价是 $a_j$。

为了让小 R “翻车”（在钱不够同时买下两者的前提下），这两个原价必须同时满足两个条件：

1. 小 R 被误导（先考虑 $i$）：糖 $i$ 的性价比要比糖 $j$ 高。即 $\frac{a_i}{1} > \frac{a_j}{2}$，也就是 $2a_i > a_j$。
2. 上帝视角更优（买 $j$ 更赚）：糖 $j$ 的总价值要比糖 $i$ 大。即 $a_j > a_i$。

合在一起就是：$a_i < a_j < 2a_i$。

---

教练的下一步引导（深挖剩余的钱）：

刚刚我们说了，小 R 买了 $i$ 没买 $j$，导致方案不是最优的。但请你仔细想想，小 R 在这整个购买过程中，他手里的钱（$m$）会经历怎样的状态，才会真的导致这种遗憾发生？

你可以分成两种情况来猜一猜：

1. 情况一（“12”型翻车）：小 R 买了糖 $i$（花了 1 元），然后遇到了糖 $j$（2 元）。此时他兜里只剩 1 元了，所以买不起糖 $j$。重点来了：如果在这之后，剩下的糖果都很贵，他这剩下的 1 块钱直到最后都没花出去！你觉得这种情况，如果把糖 $i$ 退掉，换成糖 $j$，是不是绝对更赚？

2. 情况二（“121”型翻车）：小 R 买了糖 $i$，遇到糖 $j$ 时只剩 1 元，买不起。但是！他在跳过糖 $j$ 之后，往后看，居然又遇到了一颗很便宜的糖 $k$（原价 $a_k$，定价为 1 元）。于是他花掉了最后这 1 块钱，把糖 $k$ 买了。 请问：在情况二里，小 R 总共花了 2 元，买到了糖 $i$ 和糖 $k$。如果上帝视角的我们要“打败”小 R 的方案，我们拿着这 2 元钱去买糖 $j$。我们需要满足一个什么样的大小关系，才能证明“买 $j$ 比买 $i+k$ 更赚”？（提示：比较它们的原价之和）

情况1： 不一定吧？只有当aj>ai的时候才需要退掉i换成j 。
情况2：需要满足aj>ai+ak

太严谨了！给你点个大大的赞👍！你的反驳非常精彩，这正是搞 OI 最需要的敏锐度。

你说得完全正确： 对于情况1，确实必须满足 $a_j > a_i$ 才亏，否则小 R 买 $i$ 就算是最优的了； 对于情况2，必须满足 $a_j > a_i + a_k$（也就是上帝视角的 2 块钱花在 $j$ 上，比小 R 的 2 块钱花在 $i$ 和 $k$ 上更赚），小 R 才算真正“翻车”。

既然你把这两个情况看得这么透彻，我来给你变个魔术： 我们能不能把情况1看作是情况2的一种“特殊形态”？ 想象在所有糖果的最后，隐藏着一颗**“虚空糖果 $k$”**，它的原价 $a_k = 0$，如果定清仓价为 1 元。 那么情况2的条件 $a_j > a_i + a_k$ 就顺理成章地变成了 $a_j > a_i + 0$，也就是 $a_j > a_i$——这不正好就是情况1吗！ 结论：我们只需要专门研究“121”这种翻车模型就可以了！

---

教练的下一步引导（观察“乱序”的本质）：

现在我们锁定了“121”这个罪魁祸首。我们有三个物品 $i, j, k$，它们分别被定价为 1元、2元、1元。 要想让小 R 按照 $i \to j \to k$ 的顺序去考虑它们（从而发生“买 $i$，遇 $j$ 差1块钱买不起，最后买 $k$”的悲剧），它们的性价比必须满足： $\frac{a_i}{1} > \frac{a_j}{2} > \frac{a_k}{1}$ 也就是：$a_i > \frac{a_j}{2}$ 且 $\frac{a_j}{2} > a_k$。

再加上你刚才推导出的翻车条件：$a_j > a_i + a_k$。 稍微推导一下，由于 $a_k \ge 0$，必然有 $a_j > a_i$。

好了，真正的观察开始了！请你闭上眼睛想象一下： 如果我们把所有糖果一开始只按原价 $a$ 从大到小排好队。 因为 $a_j > a_i > a_k$，所以在原始的队伍里，它们的出场顺序必然是 $j$ 在最前面，然后是 $i$，最后是 $k$。

但是，小 X 把 $j$ 定价成了 2 元，把 $i$ 和 $k$ 定价成了 1 元。 这导致 $j$ 的性价比（$a_j / 2$）缩水了！缩水到比 $a_i$ 还要小。 所以在小 R 眼里（按性价比排序），这三个物品的顺序变成了：先看 $i$，再看 $j$，最后看 $k$。

发现了吗？把一个物品定价为 2 元，本质上就是把它在队伍里“往后踢”了！ 原本排在前面的 $j$，被踢到了 $i$ 的后面。

我的提问： 为了让这个“121”悲剧精准发生，当小 R 在性价比队伍里刚好走到 $j$ 这个位置的时候，他兜里必须恰好剩下多少钱？ 换句话说，在 $j$ 被“踢”到的这个新位置之前，小 R 一共花掉了多少钱？（已知小 R 总共有 $m$ 元）

应该已经花了(原价比aj大的原价之和) 还剩下m-(原价比aj大的原价之和)

你的思路非常宏大，直接想到了排在 $j$ 前面的物品！这正是我们一会儿要计算的核心。

但我们先聚焦到小 R 面临 $j$ 的那个特定瞬间。 你想想看，$j$ 的清仓价是 2 元。

• 如果小 R 走到 $j$ 面前时，兜里有 2 元（或以上），他会怎么做？他肯定毫不犹豫就把 $j$ 买走了，那就不会翻车了。
• 如果他兜里剩 0 元呢？他确实会跳过 $j$，但是跳过之后，他也绝对买不起后面标价 1 元的 $k$ 了！

所以，为了让“遇到 $j$ 买不起，但后面刚好还能买下 1 元的 $k$” 这个剧本完美上演，小 R 遇到 $j$ 的时候，兜里必须恰好剩下几元钱？

顺着这个数字推导，既然他带了 $m$ 元出门，那他在遇到 $j$ 之前，一共恰好花掉了多少钱？（用 $m$ 来表示）

（把这个数字定死，我们就能直接列出等式，推导出绝妙的组合数学公式了！）

遇到j时应该只剩1元了，共花了m-1元

太漂亮了！一语中的！小 R 遇到 $j$ 时必须刚好花掉 $m-1$ 元，这就是整个 T2 最核心的“黄金等式”！

现在，我们把这个“花了 $m-1$ 元”的条件，放回到一开始按原价从大到小排好队的糖果序列里（即 $a_1 \ge a_2 \ge \dots \ge a_n$）。假设 $j$ 在原始队伍里的位置就是第 $j$ 个。

$j$ 被标价为 2 元，所以它在小 R 眼里的“吸引力”（性价比）缩水成了 $\frac{a_j}{2}$。

我们来看看在这个缩水后的 $\frac{a_j}{2}$ 面前，其他的糖果会怎么站队。我来问你两个关键问题：

1. 对于原来就排在 $j$ 前面的糖果（即前 $j-1$ 个，原价 $a_x > a_j$）： 无论我们给它们标价 1 元（性价比 $a_x$），还是标价 2 元（性价比 $\frac{a_x}{2}$），它们的性价比相比于 $j$ 的 $\frac{a_j}{2}$，谁更大？它们在小 R 眼里，会被排在 $j$ 的前面还是后面？它们会被小 R 买下吗？

2. 对于原来排在 $j$ 后面的糖果（原价 $a_x < a_j$）： 如果它们被标价为 2 元，性价比是 $\frac{a_x}{2} < \frac{a_j}{2}$，肯定老老实实待在 $j$ 后面。 但如果它们想**“逆袭”**，跑到 $j$ 的前面去（就像我们前面说的那个“害人精”糖果 $i$ 一样），它们必须被标价为多少元？且它们的原价 $a_x$ 必须满足什么数学条件？

试着回答这两个问题，你会发现我们马上就能把“花了 $m-1$ 元”这个条件，变成一个可以在数组上直接数个数的超级简单的方程！

问题1：因为ax>aj,所以前面的无论除以1还是除以2，性价比都比aj/2大，会被小R买到 问题2: 对于排在后面的ax<aj，需要满足ax/1>aj/2才能逆袭跑到aj前面，也就是ax>aj/2

太精彩了！你这两个回答堪称完美，完全抓住了这道题最核心的单调性和性价比的本质！

我们来把你刚才的发现，变成一个计算“花了多少钱”的终极等式。

小 R 在遇到 $j$ 之前，他考虑的物品恰好由两部分组成：

1. 原本就在 $j$ 前面的物品（共 $j-1$ 个）：因为它们的性价比实在太高了，所以小 R 肯定会把它们全买了。假设在这 $j-1$ 个物品里，有 $x$ 个被我们定价成了 2 元，剩下的 $(j-1-x)$ 个被定价成了 1 元。
2. 原本在 $j$ 后面，但成功“逆袭”跑到前面的物品：这些物品必须满足 $a > a_j/2$，且必须被定价为 1 元。假设我们从符合条件的物品中，挑了 $y$ 个定价为 1 元。

好了，请你动动笔算一下：

• 小 R 买第一部分（原本就在前面的 $j-1$ 个物品），一共花了多少钱？（用 $j$ 和 $x$ 表示）
• 小 R 买第二部分（逆袭的物品），一共花了多少钱？（用 $y$ 表示）

既然我们刚才得出了“遇到 $j$ 时恰好花了 $m-1$ 元”的黄金结论，请你把这两部分花的钱加起来，令它等于 $m-1$。化简之后，你会得到一个关于 $x$ 和 $y$ 的极其简洁的等式！

这个等式是什么？（把它敲出来，我们就离满分只差最后一步组合数学了！）

第一部分的钱是2x+1(j-1-x) 第二部分的钱是1*y 所有的花掉的钱满足这两部分相加=2x+(j-1-x)+y=m-1 化简后得到x+y=m-j

太漂亮了！你的数学直觉极其敏锐，化简出来的黄金等式 $x + y = m - j$ 绝对正确！这正是这道题最核心的灵魂。

为了和最后满分代码里的变量名完全对齐，我们在这里做一个小小的“字母替换”（请务必留意，这只是换个代号，你的逻辑完全没变）：

• 我们把那个被标价2元、惨遭跳过的物品，叫作 $i$。（原价大，在原始队伍里排在前面，也就是你刚才用的 $j$）。
• 我们把那个标价1元、成功逆袭跑到前面，并且是小R破产前买的“最后一个”物品，叫作 $j$。（原价稍小，排在后面）。

按照你刚才无懈可击的推导： 因为 $j$ 是“最后一个”被买的逆袭物品，所以它自己必占了 1 个名额，花费 1 元。 所以你公式里的 $y$（所有逆袭的1元物品），其实包含了 $j$ 本身。我们把 $j$ 单独拿出来，剩下的逆袭物品数量就是 $y' = y - 1$。 把字母替换进你的公式：$x + y' = m - i - 1$。

好了，见证奇迹的时刻到了。 我们要从哪些物品里挑出这 $x + y'$ 个物品呢？

1. 排在 $i$ 前面的物品有 $i - 1$ 个。
2. 夹在 $i$ 和 $j$ 中间的物品有 $j - i - 1$ 个。 这两拨物品加起来，总共有 $(i - 1) + (j - i - 1) = \mathbf{j - 2}$ 个物品！

我们需要从这 $j - 2$ 个物品中，任意挑选 $m - i - 1$ 个改变它们的定价（要么定为2，要么逆袭定为1）。 根据组合数学，这里的方案数直接就是：$C_{j-2}^{m-i-1}$ ！！

你现在回头看看题解里那段最核心的代码：

int N = j - 2, M = m - i - 1;
// ... (中间省略寻找 p)
ans = (ans - C[N][M] * pw[n - p + 1] % mod + mod) % mod;

是不是瞬间觉得无比亲切？这个看似天书的 $C_{j-2}^{m-i-1}$，就是被你亲手一行行推导出来的！

---

T2 的最后一步（也就是收尾）：

我们现在已经计算了 $i$ 之前、以及 $i$ 到 $j$ 之间的所有定价方案。但是别忘了，原序列在 $j$ 之后还有一堆物品呢！

我们要让小 R 彻底“翻车”，除了前面买错，最后还必须满足那个“上帝视角更优”的条件，也就是存在一个物品 $p$，使得如果我们把当初买 $i$ 的钱省下来去买 $j$ 和 $p$，会更划算： $a_i > a_j + a_p$

假设我们在数组里往后找，找到了第一个满足这个条件的物品，它的下标是 $p$。

我的最后提问： 既然小 R 在买完 $j$ 之后，兜里已经一分钱都不剩了（也就是完全破产）。那么对于排在 $p$ 后面（包括 $p$ 自己）的所有物品（一共 $n - p + 1$ 个），无论我们给它们标价 1 元还是 2 元，小 R 还能买得起吗？这会影响他最终的购买结果吗？ 如果不会影响，你觉得这 $n - p + 1$ 个物品的定价方案总数是多少？（这就解释了代码里最后那个 pw[n-p+1]，也就是 $2^{n-p+1}$ 是怎么来的了！）

对p后面的物品已经没有钱买了，不会影响结果。所以这n-p+1个物品可以任意定价（1或2），方案数是2的n-p+1次方。

太完美了！你彻底把这道题的最难点给拆解了。

最后这 $n-p+1$ 个物品因为反正都买不起了，所以无论定什么价（1元或2元），都不会影响“小 R 翻车”的既定事实。所以直接乘上 $2^{n-p+1}$。

【T2 完美收官】 你看，一长串看似复杂的题解，被我们剥丝抽茧后就成了这样： 总方案数 - 翻车的方案数。 而翻车方案，就是枚举那个“罪魁祸首”的 $i$ 和 $j$，通过 $x+y = m - j$ 算出前面的组合数 $C_{j-2}^{m-i-1}$，再乘以后面随便乱填的 $2^{n-p+1}$。 这就是 OI 的魅力，复杂的表象下藏着极简的数学逻辑！恭喜你拿下 T2！ 🎉

https://mp.weixin.qq.com/s/i8ctGeD6Lm8FQG1cj9__SA

洛谷题解

https://www.luogu.com.cn/article/mywr0ju7

公众号题解

https://mp.weixin.qq.com/s/79wkSNdKsi7TWdMxeRHdew