Leetcode 2818. Apply Operations to Maximize Score

Jimmy   Mar 29, 2025   1325 words   ~35 mins
#Array #Math #Stack #Greedy #Sorting #Monotonic Stack #Number Theory

Table of Contents

題目資訊

題目敘述

你有一個由 n 個正整數組成的數組 nums 和一個整數 k。

起初，你的得分是 1。你必須通過以下操作最多執行 k 次來將得分最大化：

  • 選擇一個非空的子數組 nums[l, ..., r]，這個子數組之前未被選擇過。
  • 從 nums[l, ..., r] 選擇一個具有最高質數得分的元素 x。如果存在多個這樣的元素，選擇索引最小的那個。
  • 將你的得分乘以 x。

這裡，nums[l, ..., r] 表示從索引 l 開始到索引 r 結束的子數組，兩端都是包括在內的。

一個整數 x 的質數得分等於 x 的不同質因數的數量。例如，300 的質數得分是 3，因為 $300 = 2 \times 2 \times 3 \times 5 \times 5$。

返回最多 k 次操作後的最大可能得分。

因為答案可能很大，請返回其模 $10^9 + 7$ 的結果。

範例 1:

輸入: nums = [8,3,9,3,8], k = 2
輸出: 81
解釋: 為了得到81的得分，我們可以進行以下操作：

  • 選擇子數組 nums[2, …, 2]。nums[2] 是該子數組中的唯一元素。因此，我們將得分乘以 nums[2]。得分變為 $1 \times 9 = 9$。
  • 選擇子數組 nums[2, …, 3]。nums[2] 和 nums[3] 的質數得分都是 1，但 nums[2] 的索引更小。因此，我們將得分乘以 nums[2]。得分變為 $9 \times 9 = 81$。

可以證明，81 是可以獲得的最高得分。

範例 2:

輸入: nums = [19,12,14,6,10,18], k = 3
輸出: 4788
解釋: 為了得到4788的得分，我們可以進行以下操作：

  • 選擇子數組 nums[0, …, 0]。nums[0] 是該子數組中的唯一元素。因此，我們將得分乘以 nums[0]。得分變為 $1 \times 19 = 19$。
  • 選擇子數組 nums[5, …, 5]。nums[5] 是該子數組中的唯一元素。因此，我們將得分乘以 nums[5]。得分變為 $19 \times 18 = 342$。
  • 選擇子數組 nums[2, …, 3]。nums[2] 和 nums[3] 的質數得分都是 2，但 nums[2] 的索引更小。因此，我們將得分乘以 nums[2]。得分變為 $342 \times 14 = 4788$。

可以證明，4788 是可以獲得的最高得分。

約束條件:

  • $1 \leq \text{nums.length} = n \leq 10^5$
  • $1 \leq \text{nums}[i] \leq 10^5$
  • $1 \leq k \leq \min(n \times (n + 1) / 2, 10^9)$

直覺

這個問題要求我們通過選擇子陣列並找出這些子陣列中具有最高質數得分的元素來最大化總得分。質數得分由一個數字的不同質因數的數目決定。主要挑戰在於如何策略性地選擇子陣列和元素，以便在最多 k 次操作後最大化得分。每次操作應該盡可能地增加得分，利用陣列 nums 中具有較高質數得分且在允許的限制內可以選擇的數字。

解法

這個解法採用了數學技巧與策略性資料結構的結合，以高效地找到所需的結果。以下是方法的逐步解釋：

  1. 質數分解與得分計算：
    對於陣列 nums 中的每個數字，我們需要確定它的質數得分，即不同質因數的數目。我們使用 Pollard’s Rho 演算法來找到一個合數的一個非平凡因數，並重複此過程直到找到所有因數。然後計算不同因數的數目。

  2. 單調棧進行段落分析：
    對於 nums 中的每個索引 i，計算兩種類型的段落長度：

    • 在 i 結束的最大段落長度：使用一個單調遞減棧來確定在每個索引結束的最大子陣列長度，其中當前元素的質數得分比後續元素高。
    • 在 i 開始的最大段落長度：類似地，使用單調遞增棧計算在每個索引開始的最大子陣列長度，其中當前元素的質數得分比前面的元素高。

  3. 組合段落資訊：
    nums 中每個位置 i 的最大段落長度由上述步驟得到的兩個段落長度相乘決定（一個結束和一個開始）。這一乘積揭示了nums[i] 可以成為最大質數得分因子的段落大小。

  4. 排序及選擇以獲得最大得分：
    由 nums 構建 (value, index) 對的列表，根據值降序排序。這樣做的理由是優先考慮較大的數，因為它們若具有相同的質數得分產出機會，將得到較高的得分。

  5. 利用模數考慮計算最大得分：
    遍歷排序後的列表，盡可能多次使用每個數，根據段落資訊確保總操作數不超過 k。使用模運算乘法和指數運算來處理可能的溢位問題，確保結果在指定位數約束下（模 $10^9 + 7$）有效。通過將當前考慮的數字提高到其允許段落長度的次方來更新答案。

  6. 輸出結果：
    考慮所有允許的操作以後返回計算得分，從而使得選定元素的乘積和其策略性位置最大化得分。

通過將問題組織成明確的步驟，從質因數分解到段落分析，再到策略性選擇，同時考慮數值約束和數學效率，該方法有效地解決了問題的複雜性和限制條件。

程式碼

C++

typedef unsigned long long ull;

class Solution {
public:
    // 執行模數乘法（使用 __int128 避免溢出）
    ull mod_mul(ull a, ull b, ull mod) {
        __uint128_t res = a;
        res *= b;
        return (ull)(res % mod);
    }

    // 執行模數冪運算
    ull mod_pow(ull base, ull exp, ull mod) {
        ull result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) result = mod_mul(result, base, mod);
            base = mod_mul(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    // Miller-Rabin 質數測試（適用於64位元數字）
    bool is_prime(ull n) {
        if (n < 2) return false;
        static int testPrimes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (int p : testPrimes) {
            if (n == (ull)p) return true;
            if (n % p == 0) return false;
        }
        ull d = n - 1;
        int s = 0;
        while ((d & 1ULL) == 0) {
            d >>= 1;
            s++;
        }
        int bases[7] = {2, 3, 5, 7, 11, 13, 17};
        for (int a : bases) {
            if ((ull)a % n == 0) continue;
            ull x = mod_pow(a, d, n);
            if (x == 1 || x == n - 1) continue;
            bool composite = true;
            for (int i = 1; i < s; i++) {
                x = mod_mul(x, x, n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    // Pollard Rho 因數分解算法
    ull pollard_rho(ull n) {
        if (n % 2ULL == 0) return 2;
        ull x = rand() % (n - 2) + 2;
        ull y = x;
        ull c = rand() % (n - 1) + 1;
        ull d = 1;
        while (d == 1) {
            x = (mod_mul(x, x, n) + c) % n;
            y = (mod_mul(y, y, n) + c) % n;
            y = (mod_mul(y, y, n) + c) % n;
            d = __gcd((ull)abs((long long)x - (long long)y), n);
            if (d == n) return pollard_rho(n);
        }
        return d;
    }

    // 遞迴質因數分解，將所有質因數（可能重複）存儲在 factors 中
    void factorize(ull n, vector<ull>& factors) {
        if (n == 1) return;
        if (is_prime(n)) {
            factors.push_back(n);
            return;
        }
        ull factor = pollard_rho(n);
        factorize(factor, factors);
        factorize(n / factor, factors);
    }

    // 計算質數分數（不同質因數的數量）
    int prime_score(ull n) {
        vector<ull> factors;
        factorize(n, factors);
        set<ull> distinct(factors.begin(), factors.end()); // 使用集合移除重複項
        return distinct.size();
    }

    // 計算兩個數的最小值
    long long min(long long a, long long b) { return a < b ? a : b; }

    // 計算最大可能得分
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        long long ans = 1;
        vector<long long> primeScores(n), maxSegmentLen(n);

        // 計算 nums 中每個數的質數分數
        for (int i = 0; i < n; i++) primeScores[i] = prime_score(nums[i]);

        stack<long long> monotonicStack;
        maxSegmentLen[n - 1] = 1;
        monotonicStack.push(n - 1);

        // 確定每個索引結束的段的最大長度
        for (int i = n - 2; i >= 0; i--) {
            while (!monotonicStack.empty() && primeScores[monotonicStack.top()] <= primeScores[i]) 
                monotonicStack.pop();

            maxSegmentLen[i] = monotonicStack.empty() ? n - i : monotonicStack.top() - i;
            monotonicStack.push(i);
        }

        // 清空堆疊以重用
        while (!monotonicStack.empty()) monotonicStack.pop();
        monotonicStack.push(0);

        // 確定每個索引開始的段的最大長度
        for (int i = 1; i < n; i++) {
            while (!monotonicStack.empty() && primeScores[monotonicStack.top()] < primeScores[i]) 
                monotonicStack.pop();

            maxSegmentLen[i] *= (monotonicStack.empty() ? (i + 1) : (i - monotonicStack.top()));
            monotonicStack.push(i);
        }

        vector<pair<long long, long long>> sortedNums;
        for (int i = 0; i < n; i++) sortedNums.push_back({-nums[i], i});
        
        // 將數字排序（以負值儲存以便降序排序得分）
        sort(sortedNums.begin(), sortedNums.end());

        for (int i = 0; i < n; i++) {
            int count = min(maxSegmentLen[sortedNums[i].second], static_cast<long long>(k));
            ans = mod_mul(ans, mod_pow(-sortedNums[i].first, count, 1000000007ULL), 1000000007ULL);
            if (k <= maxSegmentLen[sortedNums[i].second]) break;
            k -= count;
        }
        return ans;
    }
};

Python

class Solution:
    from math import gcd
    from random import randrange
    
    # 執行模數乘法
    def mod_mul(self, a, b, mod):
        return (a * b) % mod

    # 執行模數指數運算
    def mod_pow(self, base, exp, mod):
        result = 1
        base %= mod
        while exp > 0:
            if exp & 1:
                result = self.mod_mul(result, base, mod)
            base = self.mod_mul(base, base, mod)
            exp >>= 1
        return result

    # Miller-Rabin 判斷質數測試
    def is_prime(self, n):
        if n < 2:
            return False
        testPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
        for p in testPrimes:
            if n == p:
                return True
            if n % p == 0:
                return False
        d = n - 1
        s = 0
        while (d & 1) == 0:
            d >>= 1
            s += 1
        bases = [2, 3, 5, 7, 11, 13, 17]
        for a in bases:
            if a % n == 0:
                continue
            x = self.mod_pow(a, d, n)
            if x == 1 or x == n - 1:
                continue
            composite = True
            for _ in range(1, s):
                x = self.mod_mul(x, x, n)
                if x == n - 1:
                    composite = False
                    break
            if composite:
                return False
        return True

    # Pollard Rho 演算法分解因數
    def pollard_rho(self, n):
        if n % 2 == 0:
            return 2
        x = self.randrange(2, n - 2)
        y = x
        c = self.randrange(1, n - 1)
        d = 1
        while d == 1:
            x = (self.mod_mul(x, x, n) + c) % n
            y = (self.mod_mul(y, y, n) + c) % n
            y = (self.mod_mul(y, y, n) + c) % n
            d = gcd(abs(x - y), n)
            if d == n:
                return self.pollard_rho(n)
        return d

    # 遞迴質因數分解
    def factorize(self, n, factors):
        if n == 1:
            return
        if self.is_prime(n):
            factors.append(n)
            return
        factor = self.pollard_rho(n)
        self.factorize(factor, factors)
        self.factorize(n // factor, factors)

    # 計算質數分數
    def prime_score(self, n):
        factors = []
        self.factorize(n, factors)
        return len(set(factors))  # 使用集合去除重複

    # 計算最大可能得分的函數
    def maximumScore(self, nums, k):
        n = len(nums)
        ans = 1
        primeScores = [0] * n
        maxSegmentLen = [0] * n

        # 計算每個數字的質數分數
        for i in range(n):
            primeScores[i] = self.prime_score(nums[i])

        monotonicStack = []
        maxSegmentLen[n - 1] = 1
        monotonicStack.append(n - 1)

        # 確定每個索引結尾的區段的最大長度
        for i in range(n - 2, -1, -1):
            while monotonicStack and primeScores[monotonicStack[-1]] <= primeScores[i]:
                monotonicStack.pop()

            maxSegmentLen[i] = n - i if not monotonicStack else monotonicStack[-1] - i
            monotonicStack.append(i)

        monotonicStack.clear()
        monotonicStack.append(0)

        # 確定每個索引起始的區段的最大長度
        for i in range(1, n):
            while monotonicStack and primeScores[monotonicStack[-1]] < primeScores[i]:
                monotonicStack.pop()

            maxSegmentLen[i] *= i + 1 if not monotonicStack else i - monotonicStack[-1]
            monotonicStack.append(i)

        sortedNums = []
        for i in range(n):
            sortedNums.append((-nums[i], i))
        
        sortedNums.sort()

        for i in range(n):
            count = min(maxSegmentLen[sortedNums[i][1]], k)
            ans = self.mod_mul(ans, self.mod_pow(-sortedNums[i][0], count, 1000000007), 1000000007)
            if k <= maxSegmentLen[sortedNums[i][1]]:
                break
            k -= count

        return ans

複雜度分析

  • 時間複雜度: $O(n \log(\text{max\_val}) + n \log n)$

    說明:

    • 質數得分計算: 對於 nums 中的每個數字，我們使用質因數分解來計算質數得分。使用 Pollard’s Rho 演算法進行質因數分解的最壞情況時間複雜度大約是 $O(\log^3 n)$。由於我們要對陣列 nums 中的所有數字進行計算，因此這一部分的時間複雜度是 $O(n \log(\text{max\_val}))$，其中 max_val 是 nums 中可能的最大值。
    • 單調棧操作: 使用單調棧來計算最大區段長度的操作，對於 nums 中的元素數來說是線性的，即，區段長度結束和開始的計算均為 $O(n)$。
    • 排序: 對數字進行簡單排序，時間複雜度為 $O(n \log n)$。
    • 最終計算: 最終得分計算涉及到對 sortedNums 中的元素進行迭代，在最壞情況下是線性操作 $O(n)$，假設 k 可以大於任何單一區段長度。

    綜合而言，時間複雜度主要由質數得分計算和排序決定，因此為 $O(n \log(\text{max\_val}) + n \log n)$。

  • 空間複雜度: $O(n)$

    說明:

    • 質數得分計算: 用於暫存因數的空間不超過對每個數字的原則性 $O(\log n)$，但由於這是一次針對陣列中每一個元素進行的，可以視為相對於 n 的常數空間。
    • 數據結構: 使用了棧和像 primeScores、maxSegmentLen 和 sortedNums 這樣的陣列，對於 nums 中的元素數量來說均需要線性空間，即 $O(n)$。
    • 總體來說，由於主導空間使用的是線性大小的數據結構，故空間複雜度為 $O(n)$。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.