标签： 快速幂

目标

给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 7 取余。

请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 结果
1 次操作后 [2, 2, 3, 5, 6]
2 次操作后 [4, 2, 3, 5, 6]
3 次操作后 [4, 4, 3, 5, 6]
4 次操作后 [4, 4, 6, 5, 6]
5 次操作后 [8, 4, 6, 5, 6]
取余操作后 [8, 4, 6, 5, 6]

示例 2：

输入：nums = [100000,2000], k = 2, multiplier = 1000000
输出：[999999307,999999993]
解释：
操作 结果
1 次操作后 [100000, 2000000000]
2 次操作后 [100000000000, 2000000000]
取余操作后 [999999307, 999999993]

说明：

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9
• 1 <= multiplier <= 10^6

思路

有一个数组 nums，我们需要执行 k 次操作，每次操作选择数组中最小元素 min，并将它的值替换为 min * multiplier，返回最终的数组。数据范围比 3264.K次乘运算后的最终数组I 大，multiplier 也大，会溢出，需要进行取余运算。

首先 k 最大 10^9，还沿用昨天模拟的解法会超时。更重要的是，由于乘积很大，我们只能在队列中保存取余后的数据，如果还按找之前模拟来取最小元素就不对了。

我们发现，当执行一些次操作之后，所有元素都会被乘以 multiplier，当 k / n 比较大时，我们可以使用快速幂先计算出 multiplier 的 k/n 幂，然后再与元素相乘。

关键在于何时开始使用上面的思路来计算，考虑 1 2 4 8 16，multiplier 为 2，k 为 20。

2   2   4   8   16
4   2   4   8   16
4   4   4   8   16
8   4   4   8   16
8   8   4   8   16
8   8   8   8   16
16  8   8   8   16
16  16  8   8   16
16  16  16  8   16
16  16  16  16  16

可以发现 当前数组 最小值 乘以 multiplier 大于 原数组 元素的 最大值 时，后面再乘以 multiplier 就是每一个元素执行一次了。

因此我们需要先使用堆模拟前面几次操作，直到满足上面的条件。注意：堆中数据不能取模，满足条件之前堆中数据使用 long 型不会溢出。

代码

/**
 * @date 2024-12-14 10:31
 */
public class GetFinalState3266 {

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if (multiplier == 1) {
            return nums;
        }
        int mod = 1000000007;
        int n = nums.length;
        long[] mul = new long[n];
        for (int i = 0; i < n; i++) {
            mul[i] = nums[i];
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            long compare = mul[a] - mul[b];
            if (compare != 0) {
                return (int) compare;
            }
            return a - b;
        });
        long max = 0;
        for (int i = 0; i < n; i++) {
            q.offer(i);
            max = Math.max(max, nums[i]);
        }
        int i = 0;
        for (; i < k; i++) {
            if (mul[q.peek()] * (long) multiplier > max) {
                break;
            }
            Integer index = q.poll();
            mul[index] = mul[index] * multiplier;
            q.offer(index);
        }
        int remainder = k - i;
        if (remainder >= n) {
            long pow = pow(multiplier, remainder / n);
            for (int j = 0; j < n; j++) {
                Integer index = q.poll();
                int rem = remainder % n;
                mul[index] = (int) ((mul[index] * pow % mod * (j < rem ? (long) multiplier : 1)) % mod);
            }
        } else {
            for (int j = 0; j < remainder; j++) {
                Integer index = q.poll();
                mul[index] = (int) ((mul[index] * (long) multiplier) % mod);
                q.offer(index);
            }
        }
        for (int j = 0; j < n; j++) {
            nums[j] = (int) mul[j];
        }
        return nums;
    }

    public long pow(long base, int exponent) {
        long res = 1;
        int mod = 1000000007;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                res = res * base % mod;
            }
            base = base * base % mod;
            exponent >>= 1;
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

• 两个数组的长度都是 n 。
• arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
• arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
• 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余 后返回。

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

说明：

• 1 <= n == nums.length <= 2000
• 1 <= nums[i] <= 1000

思路

有一个长度为 n 正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问 有多少种拆分方法使得 arr1 非递减 且 arr2 非递增。

与昨天的 3250.单调数组对的数目I 相比，nums[i] 的最大值从 50 变成了 1000。时间复杂度大概为 O(n*m^2)，m 为 nums[i] 的最大值，如果还沿用昨天的解法就会超时。

先将昨天的题目改写为动态规划，定义 dp[i][j] 表示最后一个元素为 j，长度为 i + 1 的满足条件的 arr1 个数。由于 arr1 是非递减的，如果最后一个元素为 arr1[i] = j 那么倒数第二个元素arr1[i - 1] <= j。同时我们还要考虑到 arr2 非递增，即 arr2[i - 1] >= arr2[i]，nums[i - 1] - arr1[i - 1] >= nums[i] - arr1[i]，arr1[i - 1] <= nums[i - 1] - nums[i] + arr1[i]。综上，arr1[i - 1] <= Math.min(j, nums[i - 1] - nums[i] + j)。

经过上面的分析，dp[i][j] = Σdp[i - 1][k]，其中 k ∈ [0, Math.min(j, nums[i - 1] - nums[i] + j)]。这样写会超时，针对每个 j，我们会进行多次重复的计算。

令 d = nums[i - 1] - nums[i]，当 d >= 0 时，上界为 j，否则上界为 j + d。

考虑 nums[i - 1] < nums[i]，即 d < 0：

• 当 arr1[i - 1] = j 时，令arr2[i - 1] = nums[i - 1] - j = a
• 当 arr1[i] = j 时，arr2[i] = nums[i] - arr1[i] = nums[i - 1] - d - j = a - d，d < 0。

也就是说，当 arr1[i] 的取值与上一层一样时，arr2[i] 比上一层的值大了 |d|。为了使第 i 层 arr2 非递增，那么 arr1 的取值只能从 |d| 开始。

它们之间的约束关系是这样的，当 nums[i] 变大，arr1 第 i 层取 j 时，arr2 的第 i 层比上一层增大了 |d|，这时我们必须舍弃 [0, |d|) 的取值，因为它必定大于上一层 arr2 的最大值。然后考虑第 i 层的 arr1 取 [|d|, nums[i]] 的情况，由于第 i 层的 arr2 相比第 i - 1 层增大了 |d|，因此需要减小第 i - 1 层的 arr1，使第 i - 1 层的 arr2 增大。所以第 i 层的 j 对应第 i - 1 层的 j - |d|。

dp[i][j] 的取值类似前缀和，只不过有约束条件，并不是所有值都合法。考虑简单的情况 nums[0] == nums[1] && i == 1，

• 当 j == 0 时，dp[1][0] = dp[0][0] = 1
• 当 j == 1 时，上一层（i == 0） arr1 可以取 0、1，dp[1][1] = dp[1][0] + dp[0][1] = 2
• 当 j == 2 时，上一层（i == 0） arr1 可以取 0、1、2，dp[1][2] = dp[1][1] + dp[0][2] = 3

因此我们有 dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d])。

代码

/**
 * @date 2024-11-29 9:39
 */
public class CountOfPairs3251 {

    public static int MOD = 1000000007;

    public int countOfPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[][] dp = new int[n][1001];
        for (int i = 0; i <= nums[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            int d = Math.max(nums[i] - nums[i - 1], 0);
            for (int j = d; j <= nums[i]; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] % MOD;
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % MOD;
                }
            }
        }
        for (int i : dp[n - 1]) {
            res = (res + i) % MOD;
        }
        return res;
    }

}

性能