PROBLEM LINK:
Author: Pratik Dayama
Tester: Pratik Dayama
Editorialist: Pratik Dayama
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Modular Arithmetic, Permutations, Exponentiation by squaring.
PROBLEM:
Find total number of N digit numbers whose last K digits form a prime number and the remaining N-K digits form a palindrome. The answer is to be reported modulo 1000000007.
QUICK EXPLANATION:
The number of N-K digit palindromes is easily found to 9 * 10^((N-K-1)/2).
The number of primes of K digits can be precomputed or otherwise found, and stored.
The answer is the product of these two values, modulo 1000000007.
EXPLANATION:
The first step is to calculate the number of N-K digit palindromes. This can be easily found by permutation. The number of palindromes of some length is the possible number of permutations that its first half may contain, since the second half will simply be a mirror image of the first half. Each digit may have one of 10 values (0 to 9), except the first digit which cannot be 0. So, the number of permutations of the first half, excluding the first digit, is 10^((N-K-1)/2). This value is multiplied by 9, for the 9 possible values of the first digit.
numPalindromes = 9 * pow(10, ((N-K-1)/2))
To find 10^((N-K-1)/2) efficiently, we can use exponentiation by squaring while we do % 1000000007 at every multiplication.
The second step is to find the number of K digit primes. Since K is constrained to [1, 9], we can simply precompute or find these values and store them in an numPrimes[].
The final step is just the product of the two values:
answer = numPalindromes * numPrimes[K-1]
AUTHOR’S SOLUTION:
The solution can be found here.