題目資訊

題目編號: 2338
題目連結: Count the Number of Ideal Arrays
主題: Math, Dynamic Programming, Combinatorics, Number Theory

題目敘述

你有兩個整數 n 和 maxValue，用來描述一個理想的數組。

如果一個長度為 n 的0索引整數數組 arr 滿足以下條件，則被認為是理想的：

對於 $0 \leq i < n$ ，每個 arr[i] 的值介於 1 到 maxValue 之間。
對於 $0 < i < n$ ，每個 arr[i] 都能被 arr[i - 1] 整除。

返回長度為 n 的不同的理想數組的數量。由於答案可能會非常大，請返回它對 $10^9 + 7$ 取模的結果。

範例 1:

輸入: n = 2, maxValue = 5
輸出: 10
解釋: 以下是可能的理想數組：
- 以值 1 開始的數組 (5 個數組)：[1,1], [1,2], [1,3], [1,4], [1,5]
- 以值 2 開始的數組 (2 個數組)：[2,2], [2,4]
- 以值 3 開始的數組 (1 個數組)：[3,3]
- 以值 4 開始的數組 (1 個數組)：[4,4]
- 以值 5 開始的數組 (1 個數組)：[5,5]
總共有 5 + 2 + 1 + 1 + 1 = 10 個不同的理想數組。

範例 2:

輸入: n = 5, maxValue = 3
輸出: 11
解釋: 以下是可能的理想數組：
- 以值 1 開始的數組 (9 個數組)：
  - 無其他不同值的數組 (1 個數組)：[1,1,1,1,1]
  - 第二個不同值為 2 的數組 (4 個數組)：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
  - 第二個不同值為 3 的數組 (4 個數組)：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以值 2 開始的數組 (1 個數組)：[2,2,2,2,2]
- 以值 3 開始的數組 (1 個數組)：[3,3,3,3,3]
總共有 9 + 1 + 1 = 11 個不同的理想數組。

約束條件:

$2 \leq n \leq 10^4$
$1 \leq maxValue \leq 10^4$

直覺

此問題要求找出特定長度 $n$ 的「理想數組」的個數，其中每個元素是其前一個元素的除數且每個元素不超過最大的值 maxValue。這個問題可以通過組合數學來解決，特別是著眼於除數屬性和質因數分解特性。因為每個 arr[i] 必須可被 arr[i-1] 整除，挑戰在於有效計算符合這些條件的排列組合，尤其是在給定的 $n$ 和 maxValue 條件下。

解法

為了解決此問題，設計了一個使用組合數學的演算法，通過階乘計算和質因數分解實施。此方法包含以下主要步驟：

預計算階乘和逆元：
- 利用費馬小定理預先計算到最大限制 (maxN) 內的階乘和其模逆元，這使得模運算除法成為可能。這對於後續高效計算組合數非常關鍵。
- 通過模指數運算處理大數並防止整數溢位，特別是通過預先計算階乘及其在模 $10^9 + 7$ 下的逆元。
遍歷潛在起始值：
- 對於從 1 到 maxValue 的每個起始整數 i，評估其作為理想數組的初始值的角色。此起始整數決定了數組中後續值的潛在除數。
質因數分解：
- 對起始整數 i 進行質因數分解。通過將 i 表示為其質因子的形式，可以找到其餘數組元素的乘積或重複符合除數要求的組合。
組合及重複組合計算：
- 對於每一個質因數，使用重複組合的公式計算組合排列數： $H(n, k) = C(n + k - 1, k)$ ，其中 $C$ 代表二項係數。此公式表示將 $n$ 個不可區分的物品分配到 $k$ 個可區分的箱子的方式。
- 累加每個質因數的組合數來計算該起始整數的總組合可能性。
匯總結果：
- 計算所有可能的起始值之上的結果總和，並對 $10^9 + 7$ 取模以獲得最終的不同理想數組的計數。

通過使用階乘、逆階乘和組合數學，此方法在計算符合條件的數組時能夠有效進行，儘管輸入值在給定約束下可能很大。該實作確保所有計算均依照模 $10^9 + 7$ 的模運算進行，這是由於結果必須按照此模返回。

程式碼

C++

class Solution {
private:
    const long long MOD = 1e9 + 7;
    std::vector<long long> fact, invFact;

    // 對給定的數字n進行質因數分解的函數
    vector<pair<long long, long long>> primeFactorization(long long n) {
        vector<pair<long long, long long>> factors;
        
        // 從n中分解出因數2
        long long count = 0;
        while (n % 2 == 0) {
            count++;
            n /= 2;
        }
        if (count > 0) {
            factors.push_back({2, count});
        }
        
        // 從n中分解出所有奇數因數
        for (long long i = 3; i <= sqrt(n); i += 2) {
            count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            if (count > 0) {
                factors.push_back({i, count});
            }
        }
        
        // 如果剩餘的n大於2，則它是質數
        if (n > 2) {
            factors.push_back({n, 1});
        }

        return factors;
    }
    
    // 使用迭代指數運算計算a^b % mod的函數
    long long modPow(long long a, long long b, long long mod) {
        long long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            b /= 2;
        }
        return res;
    }
    
    // 預先計算階乘與其模反元素到maxN的函數
    void precompute(int maxN, long long mod) {
        fact.resize(maxN + 1);
        invFact.resize(maxN + 1);
        fact[0] = 1;
        for (int i = 1; i <= maxN; ++i) {
            fact[i] = fact[i - 1] * i % mod;
        }
        invFact[maxN] = modPow(fact[maxN], mod - 2, mod);  // 使用費馬小定理計算反元素
        for (int i = maxN - 1; i >= 0; --i) {
            invFact[i] = invFact[i + 1] * (i + 1) % mod;
        }
    }
    
    // 計算C(n, k) % mod的函數
    long long comb(long long n, long long k, long long mod) {
        if (k > n || k < 0) return 0;
        return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
    }
    
    // 計算H(n, k) = C(n + k - 1, k) % mod的函數
    long long repeatedComb(long long n, long long k, long long mod) {
        return comb(n + k - 1, k, mod);
    }
    
public:
    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        int maxN = 10012;  // 預計算範圍的最大值
        precompute(maxN, MOD);  // 預先計算階乘和反元素

        // 遍歷從1到maxValue的所有可能起始整數
        for (int i = 1; i <= maxValue; i++) {
            vector<pair<long long, long long>> primes = primeFactorization(i);
            long long cur_ans = 1;
            
            // 為i的每個質因數計算組合的乘積
            for (pair<long long, long long>& prime : primes) {
                cur_ans = cur_ans * repeatedComb(n, prime.second, MOD) % MOD;
            }
            
            // 將此起始整數的結果加到最終答案中
            ans += cur_ans;
            ans %= MOD;
        }

        return ans;
    }
};

Python

class Solution:
    def __init__(self):
        self.MOD = int(1e9 + 7)
        self.fact = []
        self.invFact = []

    # 函數來對給定的數字 n 進行質因數分解
    def primeFactorization(self, n):
        factors = []
        
        # 從 n 中分解出 2
        count = 0
        while n % 2 == 0:
            count += 1
            n //= 2
        if count > 0:
            factors.append((2, count))
        
        # 從 n 中分解出所有奇數
        i = 3
        while i <= int(n**0.5):
            count = 0
            while n % i == 0:
                count += 1
                n //= i
            if count > 0:
                factors.append((i, count))
            i += 2
        
        # 如果剩餘的 n 大於 2，那麼它是質數
        if n > 2:
            factors.append((n, 1))

        return factors
    
    # 函數來使用迭代冪次計算 a^b % mod
    def modPow(self, a, b, mod):
        res = 1
        while b > 0:
            if b % 2 == 1:
                res = (res * a) % mod
            a = (a * a) % mod
            b //= 2
        return res
    
    # 預先計算階乘和它們的模逆直到 maxN
    def precompute(self, maxN, mod):
        self.fact = [0] * (maxN + 1)
        self.invFact = [0] * (maxN + 1)
        self.fact[0] = 1
        for i in range(1, maxN + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.invFact[maxN] = self.modPow(self.fact[maxN], mod - 2, mod)  # 使用費馬小定理計算逆元
        for i in range(maxN - 1, -1, -1):
            self.invFact[i] = self.invFact[i + 1] * (i + 1) % mod
    
    # 函數來計算 C(n, k) % mod
    def comb(self, n, k, mod):
        if k > n or k < 0:
            return 0
        return self.fact[n] * self.invFact[k] % mod * self.invFact[n - k] % mod
    
    # 函數來計算 H(n, k) = C(n + k - 1, k) % mod
    def repeatedComb(self, n, k, mod):
        return self.comb(n + k - 1, k, mod)
    
    def idealArrays(self, n, maxValue):
        ans = 0
        maxN = 10012  # 預計算的最大範圍
        self.precompute(maxN, self.MOD)  # 預計算階乘和逆元

        # 遍歷所有可能的起始整數，從 1 到 maxValue
        for i in range(1, maxValue + 1):
            primes = self.primeFactorization(i)
            cur_ans = 1
            
            # 計算每個 i 的質因數的組合積
            for prime in primes:
                cur_ans = cur_ans * self.repeatedComb(n, prime[1], self.MOD) % self.MOD
            
            # 將此起始整數的結果加到最終答案中
            ans += cur_ans
            ans %= self.MOD

        return ans

複雜度分析

時間複雜度: $O(\sqrt{maxValue} \cdot \log(maxValue) + maxValue \cdot \log(n) + n)$
解釋:
- idealArrays 函數遍歷從 1 到 maxValue 的每一個整數，其結果為 $O(maxValue)$ 次迭代。
- 對於每一個整數 i，會調用 primeFactorization 函數。
  - primeFactorization 的時間複雜度為 $O(\sqrt{i})$ 。在最壞情況下（因數分解 maxValue），這是 $O(\sqrt{maxValue})$ 。
- repeatedComb 函數調用 comb 函數，其通過預先計算的階乘值來計算二項係數。
  - precompute 中階乘的預先計算為 $O(maxN)$ ，對應於 $O(n)$ 。二項係數本身的計算為 $O(\log(n))$ ，這是由所需的模乘次數決定的。
- 因此，綜合的時間複雜度為 $O(\sqrt{maxValue} \cdot maxValue + maxValue \cdot \log(n) + n)$ 。關於數字相對於其質數因子的密度的簡化假設導致 $O(\sqrt{maxValue} \cdot \log(maxValue) + maxValue \cdot \log(n) + n)$ 。
空間複雜度: $O(n)$
解釋:
- 空間複雜度主要由 precompute 函數中儲存階乘和逆階乘數組(fact 和 invFact)決定。
- 這些數組大小最多到 maxN，對應於 $O(n)$ ，因為 maxN 被設置為滿足問題限制，即 $n \leq 10000$ 。
- 用於在 primeFactorization 函數中儲存質因素的空間與階乘數組相比可以忽略不計，限制於 $O(\log(maxValue))$ 空間，該空間會被 $O(n)$ 因子所主導。

CS Note
En

Leetcode 2338. Count the Number of Ideal Arrays

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析