1922 统计好数字的数目

· 2025-4-13   · 次阅读   · 字数统计: 168字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

1922. 统计好数字的数目

分析

由题意可得，对于偶数位，每一位有 $5$ 种选择。对于奇数位，每一位有 $4$ 种选择

相乘得出最终的方案数，由于位数过大，需使用快速幂优化乘法速度

代码实现

class Solution {
public:
    int countGoodNumbers(long long n) {
        const int MOD = 1e9 + 7;
        auto qpow = [](long long x, long long y) {
            long long ret = 1;
            while(y) {
                if(y & 1) {
                    ret = ret * x % MOD;
                }
                x = x * x % MOD;
                y >>= 1;
            }
            return ret;
        };
        return (qpow(5, n + 1 >> 1) * qpow(4, n >> 1)) % MOD;
    }
};

复杂度分析

  • 时间复杂度：$O(\log n)$
  • 空间复杂度：$O(1)$