1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
// 1922. Count Good Numbers
#include "leetcode.h"
/*
* 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
* 1e9+7. a digit string is a string consisting of digits 0 through 9 that may
* contain leading zeros.
*/
const int MOD = 1e9 + 7;
long long _pow(long long a, long long b) {
if (!b)
return 1;
return b % 2 ? a * _pow(a, b - 1) % MOD : _pow((a * a) % MOD, b / 2);
}
int countGoodNumbers(long long n) {
long long odd = n / 2, even = n - odd;
return _pow(20, odd) * ((n % 2) ? 5 : 1) % MOD;
}
int main() {
printf("%d\n", countGoodNumbers(1)); // expect: 5
printf("%d\n", countGoodNumbers(4)); // expect: 400
printf("%d\n", countGoodNumbers(50)); // expect: 564908303
}
|