点击获取AI摘要

1922. 统计好数字的数目 M

我们称一个数字字符串是 好数字 当它满足（下标从 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 <= $10^{15}$

分析题意：

数字字符串为好数字需满足：偶数下标（0、2、4…）处的数字为偶数（0、2、4、6、8），共有 5 个选择；奇数下标（1、3、5…）处的数字为质数（只允许 2、3、5、7），共有 4 个选择。
偶数位的数量 k 为 (n + 1) // 2, 奇数位的数量为 n - k
对于长度为 $n$ 的数字字符串，偶数下标的数量为 $⌈n/2⌉ = \frac{n+1}{2}$ 向下取整, 因此总共有 $5^k$ 种可能，奇数下标的数量为 $⌊n/2⌋$ （由于数组下标从 0 开始），因此总共有 $4^{(n-k)}$ 种可能。

构造方案：

因此，好数字的总数量可表示为：

$\text{ans} = 5^{ k } \times 4^{ n-k } \mod (10^9+7)$

给定 $n$ 可能高达 $10^{15}$ ，直接计算大数幂需要使用快速幂算法（快速指数求幂），Python 内置的 pow 函数可以直接接受第三个参数来进行模运算并实现快速幂。

时间复杂度：

使用快速幂算法对大指数进行求幂取模，保证运算效率且不溢出。利用指数二进制分解实现指数运算，快速幂算法的时间复杂度为 $O(\log n)$ ，即使 $n$ 高达 $10^{15}$ 也可以在极短时间内求出结果。
使用乘法原理，将两个独立的选择相乘，即可得到所有可能性的乘积。

代码实现：

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        # 计算偶数下标的数量：
        k = (n + 1) // 2
        part5 = pow(5, k, MOD)    # 偶数下标：0, 2, 4, ...，利用内置的 pow 函数进行快速幂取模计算
        part4 = pow(4, n - k, MOD)# 奇数下标：1, 3, 5, ...
        return (part5 * part4) % MOD