Appleby Contest '20 P5 - Ridiculous Tree

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem types

Ridiculous Ray has a ridiculous tree! Oh what crazy things can he do with thee!

In his ridiculous tree, each index i (2 \le i \le N) has a parent index p_i such that 1 \le p_i < i.

Since he's so ridiculous, he wants to count the number of permutations q_1, q_2, \ldots, q_N of the numbers 1, 2, \ldots, N such that for every index i (2 \le i \le N), there exists no j (1 \le j < i) such that p_{q_j}=q_i.

As the answer can be very large, he wants you to output the prime factorization of it instead.

Constraints

For all subtasks:

2 \le N \le 4 \cdot 10^5

For all i where 2 \le i \le N, 1\le p_i<i.

Subtask 1 [10%]

2 \le N \le 7

Subtask 2 [40%]

2 \le N \le 3\,000

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains the integer N.

The next line contains the integers p_2, p_3, \ldots, p_N.

Output Specification

Let A be the number of permutations that satisfy Ray's requirements, and a_1^{b_1} \times a_2^{b_2} \times \cdots \times a_k^{b_k} be the prime factorization of A as defined under the fundamental theorem of arithmetic. The primes in the prime factorization will be ordered such that a_1 < a_2 < \ldots < a_k.

Note: If A=1, print 0 on a single line instead.

It can also be shown that A = 0 is never possible under the constraints of the problem.

On the first line, output k.

Next, output k lines of space separated integers, where the i^\text{th} line contains the integers a_i, b_i.

Sample Input 1

5
1 1 2 3

Sample Output 1

2
2 1
3 1

Sample Explanation 1

There are 6 permutations that satisfy Ray's requirements:

  • 1, 2, 3, 4, 5
  • 1, 2, 3, 5, 4
  • 1, 2, 4, 3, 5
  • 1, 3, 2, 4, 5
  • 1, 3, 2, 5, 4
  • 1, 3, 5, 2, 4

The prime factorization of 6 is 2^1 \times 3^1.

Sample Input 2

2
1

Sample Output 2

0

Sample Explanation 2

There is 1 permutation that satisfies Ray's requirements:

  • 1, 2

As the answer is 1, 0 is outputted instead.


Comments

There are no comments at the moment.