1922. Count Good Numbers

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, “2582” is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, “3245” is not good because 3 is at an even index but is not even.
Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5

Explanation: The good numbers of length 1 are “0”, “2”, “4”, “6”, “8”.

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

• 1 <= n <= 1015

---

n 小于 10 的 15 次方， 所以 O(n)的方法就不用考虑了， 要往 O(logn)方向去想, 我们先来列一下前几个位数和数量的关系

1: 5
2: 20
3: 100
4: 400
5: 2000
6: 8000
7: 40000
8: 160000

其实这个过程就是重复 ×4 和 ×5 的过程(偶数位有 0, 2, 4, 6, 8 可选， 奇数位有 2, 3, 5, 7 可选), 从上面列出的关系我们还可以看出， 位数从 2 开始， 每增加一倍， 组合的数量就会成平方增长。这样我们就可以把 n 位拆分为多个 2 的 k 次方的位数， 例如 6 = 2² + 2¹, 6 位数字的组合数量就是 4 位数字的组合数量乘以 2 位数的组合数量， 从上面的排列也可以看出这点。

---

const M: i64 = 1000000007;

impl Solution {
    
    pub fn count_good_numbers(n: i64) -> i32 {
    
        if n == 1 {
    
            return 5;
        }
	// 当前位数
        let mut digits = 2;
	// 当前组合数量
        let mut count = 20i64;
	// 如果当前位数小于目标位数
        while digits < n {
    
	    // 位数成倍增长
            let d = digits * 2;
	    // 组合数量成指数增长
            let c = count.pow(2) % M;
	    // 如果n恰巧是2的k次方则直接返回计数
            if d == n {
    
                return c as i32;
            }
	    // 如果增长后的位数大于目标位数则退出循环
            if d > n {
    
                break;
            }
            digits = d;
            count = c;
        }
	// 如果当前位数等于目标位数则直接返回当前计数
        if digits == n {
    
            return count as i32;
        }
	// 当前位数的计数乘以剩余位数的计数
        (count * Solution::count_good_numbers(n - digits) as i64 % M) as i32
    }
}