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 ii (2 \le i \le N)(2 \le i \le N) has a parent index p_ip_i such that 1 \le p_i < i1 \le p_i < i.

Since he's so ridiculous, he wants to count the number of permutations q_1, q_2, \dots, q_Nq_1, q_2, \dots, q_N of the numbers 1, 2, \dots, N1, 2, \dots, N such that for every index ii (2 \le i \le N)(2 \le i \le N), there exists no jj (1 \le j < i)(1 \le j < i) such that p_{q_j}=q_ip_{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^52 \le N \le 4 \cdot 10^5

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

Subtask 1 [10%]

2 \le N \le 72 \le N \le 7

Subtask 2 [40%]

2 \le N \le 3\,0002 \le N \le 3\,000

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains the integer NN.

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

Output Specification

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

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

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

On the first line, output kk.

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

Sample Input 1

5
1 1 2 3

Sample Output 1

2
2 1
3 1

Sample Explanation 1

There are 66 permutations that satisfy Ray's requirements:

  • 1, 2, 3, 4, 51, 2, 3, 4, 5
  • 1, 2, 3, 5, 41, 2, 3, 5, 4
  • 1, 2, 4, 3, 51, 2, 4, 3, 5
  • 1, 3, 2, 4, 51, 3, 2, 4, 5
  • 1, 3, 2, 5, 41, 3, 2, 5, 4
  • 1, 3, 5, 2, 41, 3, 5, 2, 4

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

Sample Input 2

2
1

Sample Output 2

0

Sample Explanation 2

There is 11 permutation that satisfies Ray's requirements:

  • 1, 21, 2

As the answer is 11, 0 is outputted instead.


Comments

There are no comments at the moment.