最大化仿射变换

最大化仿射变换

题目描述

有一个变量 $x$，初始时 $x = 0$。

给定 $n$ 个操作，第 $i$ 个操作定义了一个仿射变换，形式为：

$x := a_i x + b_i$

其中 $:=$ 为赋值号，$a_i$ 和 $b_i$ 均为非负整数。

你需要将这 $n$ 个操作安排一个执行顺序，并依次执行。目标是使得所有操作执行完毕后，最终 $x$ 的值达到最大。

由于最终 $x$ 的值可能会很大，请输出这个最大值对 $10^9+7$ 取模后的结果，注意不是取模后的最大值，而是对最大值取模。

输入描述:

第一行输入一个整数 $t \left(1 \le t \le 10^4\right)$，表示测试用例数量。

每个测试用例格式如下：

第一行包含一个正整数 $n \left( 1 \leq n \leq 10^6 \right)$，表示操作的总数。

接下来的 $n$ 行，第 $i$ 行包含两个非负整数 $a_i,b_i \left( 0 \leq a_i,b_i \leq 10^9 \right)$，表示第 $i$ 个操作的参数。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出描述:

输出一个整数，表示在所有可能的执行顺序中，最终 $x$ 的最大值对 $10^9+7$ 取模后的结果。

示例1

输入

5
3
2 1
1 5
3 0
4
1 1
2 1
1 2
2 2
3
0 1
0 100
1 10
4
0 0
1 0
0 1
1 1
5
4 3
2 2
1 0
3 1
5 4

输出

33
17
110
2
178

 

解题思路

  卡了一个多小时都不会的贪心，眼睁睁看着最后过了 $50$ 多个人，自己却无能为力，唉。浪费了 $2$ 个多小时去写 B 题，巨恶心的构造、模拟、分类讨论，这种题一看就知道我这辈子都不可能做出来的。还有另外一道智商构造 G 题完全不会。唉，到头来构造贪心这些完全不考算法的题根本不会，众所周知算法竞赛不考算法。

  实际看到这题是我就有预感大概率是通过交换来实现贪心的，但赛时脑抽了嫌式子太复杂懒得去推，只能说好似喵.jpg。实际上式子一点都不复杂，而且确实是通过交换来进行贪心，属于常见的贪心题型，比如耍杂技的牛，分析的方法与本题完全一样。

  把仿射的结果拆开，就会得到 $x \cdot \prod\limits_{i=1}^{n}{a_i} + \sum\limits_{i=1}^{n}{b_i \prod\limits_{j=i+1}^{n}{a_j}}$，其中由于 $x = 0$，因此实际结果为 $\sum\limits_{i=1}^{n}{b_i \prod\limits_{j=i+1}^{n}{a_j}}$。接下来我们考虑相邻的两项，即 $b_i \prod\limits_{j=i+1}^{n}{a_j}$ 和 $b_{i+1} \prod\limits_{j=i+2}^{n}{a_j}$。如果交换第 $i$ 和第 $i + 1$ 个仿射的顺序，得到的结果变为 $b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j}$ 和 $b_{i} \prod\limits_{j=i+2}^{n}{a_j}$。交换后，其他部分的结果保持不变。若要交换后的结果大于交换前的结果，那么应该满足 $$\begin{aligned} &\left( b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} \right) - \left( b_i \prod\limits_{j=i+1}^{n}{a_j} + b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \right) > 0 \\ &\left( b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} \right) - \left( b_i a_{i+1} \prod\limits_{j=i+2}^{n}{a_j} + b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \right) > 0 \\ &b_{i+1}a_i + b_i - (b_ia_{i+1} + b_{i+1}) > 0 \\ &b_{i+1}(a_i - 1) > b_i(a_{i+1} - 1) \end{aligned}$$

  因此只要相邻两个仿射变化满足 $b_{i+1}(a_i - 1) > b_i(a_{i+1} - 1)$，就可以交换这两个仿射的顺序，从而增大结果。因此，我们只需要以 $b_{i}(a_j - 1) - b_j(a_{i} - 1)$ 为关键字进行排序。如果 $b_{i}(a_j - 1) - b_j(a_{i} - 1) > 0$，则第 $i$ 个仿射变化应该排在第 $j$ 个仿射变化前。

  如果你真的仅按照上述方法进行排序并计算最终结果，虽然可以通过样例，但一交就会 WA。这题的出题人极其恶心，故意不给你边界情况的样例。实际上本题还涉及到烦人的分类讨论，需要单独考虑 $a_i = 0$ 或 $a_i = 1$ 的情况。

  需要注意的是，在上面的推导过程中，我们能除以 $\prod\limits_{j=i+2}^{n}{a_j}$ 是因为默认 $a_j > 0$。所以对于存在 $a_j = 0$ 的情况需要单独讨论。与前面的分析方法类似，我们考虑相邻两项 $b_i \prod\limits_{j=i+1}^{n}{a_j}$ 和 $b_{i+1} \prod\limits_{j=i+2}^{n}{a_j}$，并假设 $a_{i+1} = 0$，而 $a_i \ne 0$，则交换前后的结果变化量为 $$\begin{aligned} &\left( b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} \right) - \left( b_i \prod\limits_{j=i+1}^{n}{a_j} + b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \right) \\ &= b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} - b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \\ &= (b_{i+1}(a_i - 1) + b_i) \prod\limits_{j=i+2}^{n}{a_j} \geq 0 \end{aligned}$$

  因此，交换后的结果不会变差，意味着我们应始终先进行 $a_i = 0$ 的仿射变化。如果 $a_i = a_{i+1} = 0$ 呢？此时，我们应该先进行 $b_i$ 较小的仿射变化。这是因为，假设 $b_i \geq b_{i+1}$，此时有 $$\begin{aligned} &\left( b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} \right) - \left( b_i \prod\limits_{j=i+1}^{n}{a_j} + b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \right) \\ &= b_{i} \prod\limits_{j=i+2}^{n}{a_j} - b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \\ &= (b_i - b_{i+1}) \prod\limits_{j=i+2}^{n}{a_j} \geq 0 \end{aligned}$$

  因此，交换后结果不会变差。

  再考虑 $a_i = 1$ 的情况。为什么要单独考虑 $a_i = 1$ 的情况呢？这是因为 $b_j(a_i - 1) > b_i(a_j - 1)$ 理论上可以写成 $\frac{b_j}{a_j - 1} > \frac{b_i}{a_i - 1}$，而 $a_i = 1$ 这种情况会导致除数为 $0$。假设相邻两项 $a_{i+1} = 1$，且 $a_i > 1$，交换后的结果变化量为 $$\begin{aligned} &\left( b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} \right) - \left( b_i \prod\limits_{j=i+1}^{n}{a_j} + b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \right) \\ &= b_{i+1} a_i \prod\limits_{j=i+2}^{n}{a_j} + b_{i} \prod\limits_{j=i+2}^{n}{a_j} - b_{i} \prod\limits_{j=i+2}^{n}{a_j} - b_{i+1} \prod\limits_{j=i+2}^{n}{a_j} \\ &= b_{i+1}(a_i - 1) \prod\limits_{j=i+2}^{n}{a_j} \geq 0 \end{aligned}$$

  因此，交换后的结果不会变差，意味着我们应始终先进行 $a_i = 1$ 的仿射变化。如果 $a_i = a_{i+1} = 1$，交换后结果不会有变化。

  综上所述，在排序时，对于第 $i$ 个仿射和第 $j$ 个仿射，需要遵循以下规则：

• 如果 $a_i = a_j = 0$，则比较 $b_i$ 和 $b_j$，较小的应先进行仿射。
• 否则如果 $a_i = 0$ 或 $a_j = 0$，则 $a_i = 0$ 或 $a_j = 0$ 的那个应先进行仿射。
• 否则如果 $a_i = 1$ 或 $a_j = 1$，则 $a_i = 1$ 或 $a_j = 1$ 的那个应先进行仿射。
• 否则，以 $b_i (a_j - 1) - b_j (a_i - 1)$ 为关键字进行排序。

  AC 代码如下，时间复杂度为 $O(n \log{n})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e6 + 5, mod = 1e9 + 7;int a[N], b[N], p[N];void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        p[i] = i;
    }
    sort(p, p + n, [&](int i, int j) {
        if (!a[i] && !a[j]) return b[i] < b[j];
        if (!a[i] || !a[j]) return a[i] < a[j];
        if (a[i] == 1 || a[j] == 1) return a[i] == 1;
        return b[i] * (a[j] - 1ll) > b[j] * (a[i] - 1ll);
    });
    int ret = 0;
    for (int i = n - 1, t = 1; i >= 0; i--) {
        ret = (ret + 1ll * b[p[i]] * t) % mod;
        t = 1ll * t * a[p[i]] % mod;
    }
    cout << ret << '\n';
}int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  【题解】2025年广东工业大学新生赛（同步赛）：https://blog.nowcoder.net/n/4a930f0df73f4490bbe5f0babd78a0f9