难度: Medium
我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。
"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。
一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。
示例 1：
输入：n = 1 输出：5 解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
示例 2：
输入：n = 4 输出：400
示例 3：
输入：n = 50 输出：564908303
提示：
1 <= n <= 1015运行时间: 28 ms
内存: 16.7 MB
class Solution:
def countGoodNumbers(self, n: int) -> int:
def pow(base, degree, MOD):
ans = 1
cur = 1
while cur <= degree:
if cur & degree:
ans = ans * base % MOD
base = base * base % MOD
cur <<= 1
return ans
return pow(5, n - n // 2, 10 ** 9 + 7) * pow(4, n // 2, 10 ** 9 + 7) % (10 ** 9 + 7)
题解采用了数学的方法来解决问题。首先，观察到好数字的定义：偶数下标的数字必须是偶数（0, 2, 4, 6, 8共5种选择），奇数下标的数字必须是质数（2, 3, 5, 7共4种选择）。对于长度为n的字符串，偶数下标的位置有 n - n // 2 个（例如长度为4，偶数位置有2个，长度为5，偶数位置也有3个），而奇数下标的位置有 n // 2 个。因此，长度为n的好数字的总数可以表示为 5的(n - n // 2)次方 乘以 4的(n // 2)次方。由于结果可能非常大，使用了模10^9 + 7的快速幂算法来计算这两个数的幂，并最终计算出结果。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def countGoodNumbers(self, n: int) -> int:
def pow(base, degree, MOD):
ans = 1
cur = 1
# 使用快速幂算法计算(base^degree) % MOD
while cur <= degree:
if cur & degree:
ans = ans * base % MOD
base = base * base % MOD
cur <<= 1
return ans
# 计算好字符串的总数，使用快速幂分别计算5^(n - n // 2) 和 4^(n // 2)
return pow(5, n - n // 2, 10 ** 9 + 7) * pow(4, n // 2, 10 ** 9 + 7) % (10 ** 9 + 7)
快速幂算法相比于普通的幂计算具有明显的时间效率优势。普通的幂计算通过连续乘法来计算base的degree次方，其时间复杂度为O(degree)，这在degree非常大时会非常耗时。快速幂算法通过将幂次拆分成二进制形式，并利用幂的性质（a^b = (a^(b/2))^2）来减少计算步骤，将时间复杂度降低到O(log(degree))。这使得即便对于非常大的幂次，如题目中的10^15，也能在可接受的时间内完成计算。
在处理大数运算时，尤其是在计算机科学中，直接操作非常大的数值会导致溢出和处理速度下降的问题。MOD为10^9 + 7是一个常用的大素数，对结果进行取余操作可以保证结果始终在一个固定的范围内，避免溢出并减少计算量。此外，取模运算在数学和计算机科学中广泛应用于散列函数、加密算法等领域，能够保证结果的均匀性和安全性。
在题目中，好数字的定义涉及到数字在偶数和奇数位置上的特定要求。偶数下标的位置必须是偶数数字（0, 2, 4, 6, 8），共有5种选择；奇数下标的位置必须是质数（2, 3, 5, 7），共有4种选择。因此，对于长度为n的数字串，偶数下标的位置有5种选择，奇数下标的位置有4种选择。5^(n - n // 2)计算的是偶数下标的所有可能组合，而4^(n // 2)计算的是奇数下标的所有可能组合。
为了处理如此大的n值（可达10^15），算法需要非常高效。快速幂算法在这里发挥了关键作用，因为它能够在O(log(n))的时间复杂度内计算幂。此外，由于结果使用了模10^9 + 7运算，这进一步保证了每步计算中涉及的数值不会过大，从而避免了潜在的性能问题。这些优化措施共同确保了算法即便在极端情况下也能保持高效率和稳定性。