## 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