blob: 639c723f312ff67ef72d8c4da80e9ad7841930bd (
plain)
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
33
34
35
36
37
38
39
|
// 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.
*/
static int mod = 1e9 + 7;
long long mod_exp(long long n, long long e) {
int res = 1;
n %= mod;
while (e > 0) {
if (e & 1)
res = res * n % mod;
e >>= 1;
n = n * n % mod;
}
return res;
}
int countGoodNumbers(long long n) {
long long a = mod_exp(5, (n + 1) / 2);
long long b = mod_exp(4, n / 2);
return (int)((a * b) % mod);
}
int main() {
printf("%d\n", countGoodNumbers(1)); // expect: 5
printf("%d\n", countGoodNumbers(4)); // expect: 400
printf("%d\n", countGoodNumbers(50)); // expect: 564908303
}
|