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 Less than 10 Of 15 Power , therefore O(n) There is no need to consider the method of , Want to go O(logn) Direction to think , Let's first list the relationship between the first few digits and quantity

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

In fact, this process is repetition ×4 and ×5 The process of ( Even digits have 0, 2, 4, 6, 8 Optional , Odd digits have 2, 3, 5, 7 Optional ), From the relationships listed above, we can also see , The number is from 2 Start , Every doubling , The number of combinations will increase squarely . So we can n Bits are split into multiple 2 Of k The number of digits to the power of , for example 6 = 2² + 2¹, 6 The combined number of digits is 4 Multiply the number of combinations of digits by 2 Number of combinations of digits , This can also be seen from the above arrangement .

---

const M: i64 = 1000000007;

impl Solution {
    
    pub fn count_good_numbers(n: i64) -> i32 {
    
        if n == 1 {
    
            return 5;
        }
	//  Current digit 
        let mut digits = 2;
	//  Current combination quantity 
        let mut count = 20i64;
	//  If the current digit is less than the target digit 
        while digits < n {
    
	    //  The number of digits has doubled 
            let d = digits * 2;
	    //  The number of portfolios increases exponentially 
            let c = count.pow(2) % M;
	    //  If n Happen to be 2 Of k The power returns the count directly 
            if d == n {
    
                return c as i32;
            }
	    //  If the number of digits after growth is greater than the target number, exit the cycle 
            if d > n {
    
                break;
            }
            digits = d;
            count = c;
        }
	//  If the current digit is equal to the target digit, the current count is returned directly 
        if digits == n {
    
            return count as i32;
        }
	//  Multiply the current digit count by the remaining digit count 
        (count * Solution::count_good_numbers(n - digits) as i64 % M) as i32
    }
}