P14636 [NOIP2025] 清仓甩卖 / sale

原题链接：P14636 [NOIP2025] 清仓甩卖 / sale

Tag：组合数学、范德蒙德卷积

题目描述

小 X 的糖果促销策略很成功，现在糖果店只剩下了 \(n\) 颗糖果， 其中第 \(i\) (\(1 \le i \le n\)) 颗糖果的原价为 \(a_i\) 元。 小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 1 元或 2 元。 设第 \(i\) (\(1 \le i \le n\)) 颗糖果的清仓价格为 \(w_i \in \{1,2\}\) 元， 则它的性价比被定义为原价与清仓价格的比值，即 \(\frac{a_i}{w_i}\)。

小 R 又带了 \(m\) 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大， 于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。 具体地，若小 R 在考虑第 \(i\) (\(1 \le i \le n\)) 颗糖果时剩余的钱至少为 \(w_i\) 元，则他会购买这颗糖果； 否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则小 R 会先考虑原价较高的糖果； 若存在两颗糖果的性价比与原价均相同，则小 R 会先考虑编号较小的糖果。

例如，若小 X 的糖果商店剩余 3 颗糖果， 原价分别为 \(a_1=1\)，\(a_2=3\)，\(a_3=5\)， 而清仓价格分别为 \(w_1=w_2=1\)，\(w_3=2\)，则性价比分别为 \(1, 3, \frac{5}{2}\)。 因此小 R 会先考虑第 2 颗糖果，然后考虑第 3 颗糖果，最后考虑第 1 颗糖果。

小 R 想知道，在小 X 的所有 \(2^n\) 种定价方案中， 有多少种定价方案使得他按照上述购买策略能购买到的糖果的原价总和最大。 你需要帮助小 R 求出满足要求的定价方案的数量。由于答案可能较大， 你只需要求出答案对 \(998,244,353\) 取模后的结果。

分析

首先我们要分析明白一件事： 就是题目给出的贪心策略在什么时候是错的。

因为具体的花费只可能有 \(1\) 和 \(2\)，所以错误的情况只可能是： 我们有一个 \(1+1\) 买了 \(2\) 个的方案，但是实际上存在一个比他们两个原价加起来都要大的 \(2\) 我们没有买。

我们接下来假设这个 \(2\) 的糖果是 \(X\)， 其余的两个 \(1\) 分别是 \(Y,Z\)。

那么接下来我们从两个方面去考虑。

第一个方面： 首先我们考虑 \(Y\)，因为它最后只值一块钱，那么其性价比就是 \(\displaystyle\frac{Y}{1}\)。 而对于 \(X\)，其性价比就是 \(\displaystyle\frac{X}{2}\)， 那么如果我们想要让 \(Y\) 排在 \(X\) 的前面，就必须要有：

\[ 2Y < X \Leftrightarrow X < 2Y \]

注意这里的性价比我们是乘以二之后讨论的，之后我们还会用到。

第二个方面： 如果把 \(Y,Z\) 换成 \(X\) 是更好的，那么其实就要满足（下文我们规定 \(Y\) 是两个 \(1\) 元中较贵的一个）：

\[ X > Y + Z \]

所以造成贪心出错的核心不等式就是：

\[ Y + Z < X < 2Y \]

因为题目中糖果的顺序并不重要，所以我们可以非常自然地对数组排序一下。 那么我们把 \(a\) 进行排序，变成：

\[ b_1 \leq b_2 \leq \cdots \leq b_n \]

我们先考虑 \(X,Y\)，我们用 \(i\) 对应 \(Y\)，用 \(j\) 对应 \(X\)， 那么我们枚举 \((i,j)\) 这个对的条件就是：

\[ b_j < 2b_i \]

但是 \(Z\) 要如何处理？ 其实对于我们刚才的 \(Y = b_i,X = b_j\)，\(Z\) 必须要满足：

\[ Z < X - Y \Leftrightarrow b_p < b_j - b_i \]

而因为数组是有序的，那么上面的 \(b_p\) 肯定是数组 \(b\) 上的一段前缀。 那其实我们就可以使用这个办法来找到这个 \(k\)：

while (k < j - 1 && b[i] + b[k + 1] < b[j]) k++;

当我们拿到了这个前缀之后，我们进一步思考会发现一个事实： 那就是我们对于这前 \(k\) 个，不管怎么标价，都不会影响 \(X > Y + Z\) 这个事实。 所以小于 \(X-Y\) 的这一段，全部随便定价就可以了，方案数自然是 \(2^k\)。

我们再来回顾一下 \(X\) 和 \(Y\) 的定义， \(X\) 是因为贪心被错过的 \(2\) 元糖果，而 \(Y\) 是因为贪心被选到的 \(1\) 元糖果。

那么如果我们要错过 \(2\) 元的 \(X\)， 也就是说当我们看到 \(X\) 的时候，我们必须剩下 \(0\) 元或者 \(1\) 元。 也就是说，在我们看到 \(X\) 之前，需要花掉 \(m-1\) 元。

接下来我们需要做一个分类讨论， 因为我们发现，当我们固定了 \((i,j)\) 之后， 整个数组相当于被分成了三段，足够小的哪一段我们已经分析过了， 剩下的两段是足够大的，和位于 \(i\) 和 \(j\) 之间的。

我们先考虑「足够大」的一段，我们称其为组 \(A\)。 其实足够大指的就是数值比 \(X\) 还要大的一段， 也就是下标满足 \(> j\) 的一段。

那么对于这些 \(b > b_j\)， 根据「乘以二的性价比」 我们设标价 \(w = 1\)，那么分数就是 \(2b\)， 如果标价 \(w = 2\)，那么分数就是 \(b\)。 我们发现 \(2b\) 和 \(b\) 都依然满足 \(>b_j\)， 也就是说这一组「足够大」的，无论标 \(1\) 还是 \(2\)， 最后都依然要排在 \(X\) 前被选。

而这一组的数量为 \(|A| = n - j\)。

最后一组就下标位于 \(i\) 和 \(j\) 之间的， 我们设这些值为 \(b_k \in (b_i,b_j)\)， 而且我们根据前面的限制，这里只考虑 \(b_j < 2b_i\)， 因此 \(b_k \geq b_i > b_j / 2\)。

那么对于这部分，如果我们标 \(1\) 元，分数就是 \(2b_k > b_j\)，要排到 \(X\) 之前了。 而如果我们标 \(2\) 元，分数 \(b_k < b_j\)，就会在 \(X\) 之后。

组 \(B\) 的数量是 \(|B| = j - i - 1\)。

我们最后一个需要解决的问题在于，花掉 \(m-1\) 元这个事情。

我们设 \(x\) 为组 \(A\) 中标 \(2\) 元的个数，\(y\) 为组 \(B\) 中标了 \(1\) 的数量。 那么在我们看到 \(X\) 之前花掉的钱，就可以这样去算：

• 组 \(A\)：不管怎么标都在 \(X\) 前面，而且至少花费 \(1\)，那就相当于先花了 \(|A|\)，有 \(x\) 个花了 \(2\) 元，就多花了 \(x\) 元。

• 组 \(B\)：只有标 \(1\) 的会跑到 \(X\) 的前面，并且花钱，所以贡献了 \(y\)。

• 再加上 \(Y\) 是必定要被买的那个 \(1\) 元糖果。

所以我们可以把「看到 \(X\) 时剩下 \(1\) 元」写成方程：

\[ |A| + x + y + 1 = m - 1 \]

移项则有 \(x + y = m - 2 - |A| = m - 2 -(n - j)\)

我们终于可以开始统计方案了：

• 组 \(A\)：从 \(|A|\) 个里选择 \(x\) 个标价为 \(2\)，方案数是 \(\displaystyle {|A|}\choose x\)

• 组 \(B\)：从 \(|B|\) 个里选择 \(y\) 个标价为 \(1\)，方案数是 \(\displaystyle {|B|}\choose y\)

而我们之前得到了 \(x + y = m - 2 - (n - j)\)

所以总共的方案数就是：

\[ \sum_x {{|A|}\choose x} \times {{|B|}\choose \text{sum} - x} \]

而这正是范德蒙德卷积的形式：

\[ \sum_{i=0}^k {n \choose i} \times {{n+m} \choose k - i} = {{n+m} \choose k} \]

于是我们非常自然地把之前的式子变成：

\[ \sum_x {{|A|}\choose x} \times {{|B|}\choose \text{sum} - x} = {{|A| + |B|} \choose \text{sum}} \]

而且：

\[ |A| + |B| = (n - j) + (j - i - 1) = n - i - 1。 \]

因此：

\[ {{|A| + |B|} \choose \text{sum}} = {{n-i-1}\choose {m-2-(n-j)}} \]

我们只要求出这个组合数就可以了。

在实现方面，我们之前提到的 \(2^k\) 可以直接线性处理， 组合数采用预处理阶乘和阶乘逆元的写法，我们只需要排序后枚举 \((i,j)\) 这样的对， 具体的前缀长度我们用双指针维护，总体复杂度 \(O(n^2)\)

代码实现

（省去了组合数和快速幂部分）

void IHaveNoLimitation() {
    int c, t;
    cin >> c >> t;
    const int MAXN = 5000;
    Comb comb(MAXN);
    vector<long long> pw(MAXN + 1);
    pw[0] = 1;
    for (int i = 1; i <= MAXN; i++) pw[i] = pw[i - 1] * 2 % MOD;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        std::sort(a.begin() + 1, a.end());
        long long bad = 0;
        for (int i = 1; i <= n; i++) {
            int k = 0;
            for (int j = i + 1; j <= n; j++) {
                if (a[i] * 2 > a[j] && a[i] != a[j]) {
                    while (k < j - 1 && a[i] + a[k + 1] < a[j]) k++;
                    int sum = m - 2 - (n - j);
                    int cnt = n - i - 1;
                    if (0 <= sum && sum <= cnt) {
                        bad = (bad + pw[k] * comb.C(cnt, sum)) % MOD;
                    }
                }
            }
        }
        long long ans = (pw[n] - bad) % MOD;
        if (ans < 0) ans += MOD;
        cout << ans << endl;
    }
}

日志

本页面创建于 2025/12/18 16:45

UPD-1：2025/12/18 16:57

在Heltion、foreverlasting、 yhx-12243的指点下进行了格式修改，避免歧义。