【LeetCode周赛248】C LeetCode 5802. 统计好数字的数目

摘要：
经典模意义下快速幂应用。

题目

我们称一个数字字符串是 好数字 当它满足（下标从 $0$ 开始）偶数下标处的数字为偶数且奇数下标处的数字为质数（$2$，$3$，$5$ 或 $7$）。

比方说，$2582$ 是好数字，因为偶数下标处的数字（$2$ 和 $8$）是偶数且奇数下标处的数字（$5$ 和 $2$）为质数。但 $3245$ 不是好数字，因为 $3$ 在偶数下标处但不是偶数。

给你一个整数 $n$ ，请你返回长度为 $n$ 且为好数字的数字字符串总数。由于答案可能会很大，请你将它对 $10^9 + 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}$

快速幂

对于长度为 $n$ 的数字，偶数位对应着 $0, 2, 4, 6, 8$ 共 $5$ 种选择；奇数位对应着 $2, 3, 5, 7$ 共 $4$ 种选择。

偶数位共有 $\lceil n / 2 \rceil$ 个，奇数位共有 $\lfloor n / 2 \rfloor$ 个。

那么答案应该是 $5^{\lceil n / 2 \rceil} \times 4^{\lfloor n / 2 \rfloor} \bmod (10^9 + 7)$.

使用模意义下的快速幂可以在 $O(log(\lceil n / 2 \rceil + \lfloor n / 2 \rfloor))$ 复杂度内算出。

using LL = long long;
constexpr int MOD = 1'000'000'007;

class Solution {
public:
    inline LL ksm(LL a, LL b, LL MOD) {
        LL res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    int countGoodNumbers(LL n) {
        LL even = n + 1 >> 1;
        LL odd = n >> 1;
        return (ksm(5, even, MOD) * ksm(4, odd, MOD)) % MOD;
    }
};

原题链接： LeetCode 5802. 统计好数字的数目