1922. 统计好数字的数目(中等)

Posted on In Views:

1，问题描述

1922. 统计好数字的数目

难度：中等

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

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

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

示例 1：

1
2
3
输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。

示例 2：

1
2
输入：n = 4
输出：400

示例 3：

1
2
输入：n = 50
输出：564908303

提示：

  • 1 <= n <= 10^15

2，思考过程

​ 全排列+快速冥

lc50-3-c.png

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countGoodNumbers(long n) {
        return (int)((pow(5, (n+1)/2) * pow(4, n/2))%1000000007);
    }
    long mod = 1000000007;
    private long pow(long x, long n){
        long res = 1;
        long mul = x;
        while (n > 0) {
            if (n % 2 == 1) {
                res = res * mul % mod;
            }
            mul = mul * mul % mod;
            n /= 2;
        }
        return res;
    }
}