PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Sieve of Eratosthenes, Dynamic Programming
PROBLEM
You are given an integer N. Count the number of prime permutations of size N. A permutation of integers between 1 and N is called a prime permutation of size N if for all i between 1 and N, inclusive, the i-th integer is the X-th smallest integer in the first i integers, where X is 1 or a prime number.
QUICK EXPLANATION
Let pperm[i] = the number of prime permutations of size i. Let’s calculate pperm[i]. The last number (i.e., the i-th number) has to be the smallest number or the X-th smallest number for some prime number X. Therefore, we have (1 + primes[i]) choices for the last number, where primes[i] is the number of prime numbers not greater than i. The rest of the first i - 1 numbers can be permuted in any of the pperm[i-1] ways. In other words,
pperm[1] = 1 pperm[i] = (1 + primes[i]) Ă— pperm[i-1]
The answer is pperm[N]. We can precompute the values of pperm[i] for all i between 1 and 5,000,000, inclusive, and then answer each test case in O(1) time.
EXPLANATION
First, let’s generate prime numbers between 1 and 5,000,000, inclusive. Let isPrime[i] = whether or not i is prime number. We can use Sieve of Eratosthenes algorithm. If you forgot, the pseudocode is as follows.
maxN = 5000000
isPrime[1] = false
for i = 2; i <= maxN; i++:
isPrime[i] = true
for i = 2; i Ă— i <= maxN; i++:
if isPrime[i]:
for j = i Ă— i; j <= maxN; j = j + i:
isPrime[j] = false
After that, build primes[] array, where primes[i] is the number of prime numbers not greater than i. We can use a dynamic programming approach: primes[i] is exactly equal to primes[i-1], plus 1 if i is a prime number.
primes[0] = 0
for i = 1; i <= maxN; i++:
primes[i] = primes[i-1] + (isPrime[i] ? 1 : 0)
Now, let’s solve the original problem. There is one important observation here. Actually, we do not care whether the numbers in the permutation are distinct integers between 1 and N, inclusive. We only care about the relative rank of each number (see the definition of prime permutation). Therefore, the N integers actually can be any N distinct integers.
We will use dynamic programming approach. Let the subproblem be pperm[i] = the number of prime permutations of i distinct numbers. The base case is pperm[1] = 1, since a single number is always a valid prime permutation.
Let’s calculate pperm[i] for i > 1. Consider the last position (i.e., the i-th position). From the definition of a prime permutation, the number in the last position has be the smallest number, or the X-th smallest number for some prime number X. Therefore, there are (1 + primes[i]) choices for the number in the last position. After we fix the last number, we have to place the remaining i - 1 numbers in the first i - 1 positions in such a way that the whole permutation is a prime permutation. To accomplish that, by definition, the numbers in the first i - 1 positions have to form a prime permutation as well.
The remaining i - 1 numbers are obviously i - 1 distinct integers. By the previous dynamic programming definition, the number of ways to permute i - 1 distinct numbers to form a prime permutation is pperm[i-1]. Therefore,
pperm[i] = (1 + primes[i]) Ă— pperm[i-1]
The answer for a particular N is of course pperm[N].
We have to precompute all values of pperm[i] for all i between 1 and 5,000,000, inclusive. The time complexity of the precomputation is dominated by the complexity of Sieve of Eratosthenes, O(N log N log log N), where N = 5,000,000 in this problem. After that, we can answer each test case in O(1) lookup time.
Do not forget to perform all calculations modulo 1,000,000,007.
SETTER’S SOLUTION
Can be found here
TESTER’S SOLUTION
Can be found here
