題目資訊

• 題目編號: 1922
• 題目連結: Count Good Numbers
• 主題: Math, Recursion

題目敘述

一個數字字串是好的，如果在偶數索引位置的數字是偶數，而在奇數索引位置的數字是質數（2, 3, 5, 或 7）。

• 例如，"2582"是好的，因為在偶數位置上的數字（2 和 8）是偶數，而在奇數位置上的數字（5 和 2）是質數。然而，"3245" 不是好的，因為數字 3 在偶數索引位置，但不是偶數。

給定一個整數 $n$，請返回長度為 $n$ 的好的數字字串的總數。由於答案可能很大，請返回它對 $10^9 + 7$ 的取模結果。

一個數字字串是由數字 $0$ 到 $9$ 組成的字串，且可以包含前導零。

範例 1:

輸入: n = 1
輸出: 5
解釋: 長度為 1 的好的數字是 "0", "2", "4", "6", "8"。

範例 2:

輸入: n = 4
輸出: 400

範例 3:

輸入: n = 50
輸出: 564908303

限制條件:

• $1 \leq n \leq 10^{15}$

直覺

此問題涉及到製作數字字串，其中要求偶數索引上的數字必須是偶數，而奇數索引上的數字必須是質數，這些質數必須來自集合 ${2, 3, 5, 7}$。給定這些限制條件，我們需要一個有效的方法來計算這些滿足條件的數字字串的數量，而不需要顯式生成它們。此方法可利用組合數學及模數運算來計算有效組合的數量，同時應用這些數字的特性。

解法

為了解決此問題，我們可以根據索引劃分數字字串：

1. 偶數索引 : 允許的數字為 ${0, 2, 4, 6, 8}$，因此每一個偶數索引都有5種選擇。
2. 奇數索引 : 允許的數字為 ${2, 3, 5, 7}$，因此每一個奇數索引都有4種選擇。

考慮到字串的長度為 $n$，其中大約一半的數字會落在偶數索引，而另一半則落在奇數索引。

1. 偶數位置的計算 : 偶數索引位置的數量為 $\lceil n/2 \rceil$。對於每個這樣的位置，我們有5個可用數字，故有 $5^{\lceil n/2 \rceil}$ 種可能的組合。

2. 奇數位置的計算 : 奇數索引位置的數量為 $\lfloor n/2 \rfloor$。對於每個這樣的位置，我們有4個可用數字，故有 $4^{\lfloor n/2 \rfloor}$ 種可能的組合。

3. 總組合數 : 滿足條件的數字字串總數為偶數和奇數索引位置組合的乘積，即為 $5^{\lceil n/2 \rceil} \times 4^{\lfloor n/2 \rfloor}$。

4. 處理較大 $n$ 值 : 鑑於 $n$ 可以大到 $10^{15}$，直接計算大次方可能導致計算及存儲挑戰。因此，我們使用快速模數冪運算以有效處理這些大次方，並且確保結果可控。最終答案必須進行模運算以 $10^9 + 7$。

函數 fast_pow_mod 實現了快速模數冪運算，通過一種稱為平方乘法法的方式來計算 $(\text{base}^\text{exp}) \bmod \text{mod}$。這是一種效率為 $O(\log \text{exp})$ 的方法：

• 初始時將結果設置為1。
• 當指數大於0時：
  • 如果指數是奇數，將當前結果乘以基數並取模。
  • 將基數平方並取模。
  • 使用右移將指數除以2。

此方法確保我們可以在 $n$ 非常大的情況下處理大指數。函數 countGoodNumbers 最後計算偶數和奇數索引的可能性乘積並返回模 $10^9 + 7$ 的結果。

程式碼

C++

#define MOD (long long)(1e9+7)

class Solution {
private:
    // 函數：執行快速模指數運算
    long long fast_pow_mod(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod; // 起始時將基數化簡為模
        while (exp > 0) {
            if (exp & 1) { // 檢查當前指數是否為奇數
                result = result * base % mod; // 如果指數是奇數，將結果乘以基數
            }
            base = base * base % mod; // 將基數平方
            exp >>= 1; // 將指數右移 1 位（除以 2）
        }
        return result;
    }
public:
    // 函數：計算長度為 n 的良好數字字串
    int countGoodNumbers(long long n) {
        // 計算良好數字字串的總數
        // 通過乘以偶數和奇數索引的可能性
        return (fast_pow_mod(5, (n + 1) / 2, MOD) * fast_pow_mod(4, n / 2, MOD)) % MOD;
    }
};

Python

class Solution:
    # 定義模數常數
    MOD = int(1e9 + 7)
    
    # 用於快速模指數運算的函式
    def fast_pow_mod(self, base, exp, mod):
        result = 1
        base %= mod  # 一開始就將基數取模
        while exp > 0:
            if exp & 1:  # 檢查當前的指數是否為奇數
                result = result * base % mod  # 如果指數是奇數，則結果乘上基數
            base = base * base % mod  # 基數自乘
            exp >>= 1  # 將指數右移1位（等於除以2）
        return result
    
    # 計算長度為 n 的優良數字字串的數量
    def countGoodNumbers(self, n):
        # 計算優良數字字串的總數
        # 通過計算偶數和奇數索引的可能性來相乘
        return (self.fast_pow_mod(5, (n + 1) // 2, self.MOD) * self.fast_pow_mod(4, n // 2, self.MOD)) % self.MOD

複雜度分析

• 時間複雜度: $O(\log n)$

  代碼中的核心操作是 fast_pow_mod 函數，該函數執行快速模指數運算。此函數的時間複雜度是 $O(\log \text{exp})$，其中 exp 是指數。在此代碼中，該函數在 countGoodNumbers 中被調用兩次，指數分別為 $\lceil \frac{n}{2} \rceil$ 和 $\lfloor \frac{n}{2} \rfloor$。由於這兩者均約為 $n/2$，因此整體時間複雜度為 $O(\log n)$。

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

  空間複雜度為 $O(1)$，因為演算法所需的空間量是恆定的，並不依賴輸入大小 $n$。所用的局部變量僅為少數的整數用於計算。算法的遞迴深度不會隨著 $n$ 的增長而增加，從而保證了恆定的空間使用。