题目浅析

  • 想查看原题可以点击题目链接。
  • 简单地说，就是给一个数字 n，要求给出满足特定要求的位数为 n 的数字个数，该要求是（从零开始）偶数下标为偶数且奇数下标为质数。

思路分享

  • 刚开始本想用数位 dp，但细算觉着计算量还是太大，本地对于每一位实际上没有太多限制，但是总数量非常大，只好看看题解思路。
  • 本题本质上可以用组合数学算出，一个 n 位的数字，必定有 (n/2) 取下位偶数下标，剩下奇数下标，偶数下标有 5 个可能，奇数下标有 4个可能，所以只要计算出 5^((n+1)/2) + 4^(n/2) 即可（这里的 / 为整除）。
  • 注意，由于数字很大，有两个要点，一个是快速幂，二是如何正确取模。

快速幂

  • 快速幂的本质是通过把普通的累乘，转化为平方乘积，复杂度由O(n)降到了O(log(n))。
  • 比如，计算 2 的 13 次方，13 的二进制表示为 1101，2 的 13 次方可以视为 2^4 * 2^3 * 2^1。
  • 转化为程序的自然语言，就是不断判断次方数的最后一位是否为 1，是的话，将结果乘上当前底数，每次次方数右移时，底数则平方。
  • 如果指数为负数，则将指数取反得正数，同时把底数求倒数。

    https://leetcode.cn/problems/powx-n/

取模方法

  • 这里涉及到不少离散数学的知识，简单地说，除了 python 以外的语言如果先求解结果再取模一般都会因为溢出出错。因此需要通过下面方法来解决。
  • 对于加法 a + b，可以这么取模：a + b % MOD
  • 对于减法 a - b，可以取模：(a - b + MOD ) % MOD
  • 对于乘法 a*b*c, 可以取模：(a * b % MOD) * c % MOD
  • 除法尚未理解，姑且放着，用到自然会学：）

    https://leetcode.cn/discuss/post/3584387/fen-xiang-gun-mo-yun-suan-de-shi-jie-dan-7xgu/

代码解答（强烈建议自行解答后再看）

  • 参考的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    const int MOD = 1000000007;
    long long qpow(long long x, long long n) {
        long long ans = 1;
        while(n) {
            if (n&1) {
                ans = ans * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return ans;
    }
    int countGoodNumbers(long long n) {
        return qpow(5, (n+1)/2) * qpow(4, n/2) % MOD;
    }
};