### PROBLEM LINK:

**Author:** Denis Anishchenko

**Tester:** Hasan Jaddouh

**Editorialist:** Sarv Shakti Singh

**Difficulty:** Medium

**Prerequisites:** Combinatorics

**Problem:** You have a bunch of cycles, each containing some nodes. For each node, starting from the node, travel across the cycle until you reach the same node. Now, you have an array `A`

of N elements, which means that the `i`

th node occurs `A*`

times after applying each operation. You need to tell how many ways are there to form those cycles that are consistent with array `A`

.

**Explanation:** Let’s clear up the problem statement given on the contest page. Gritukan writes a permutation `P`

of `N`

numbers such that, for each node i, visit `P*`

, then `P[P*]`

, and repeat this until you reach `i`

again. Now, this guarantees that the permutation has each node in a cycle exactly once. Proof?

- Each node is a part of a
**cycle**, otherwise we will never reach the start node again. - Each node is part of a cycle
**exactly once**, since we can move to only one node from a current node.(Just think about it!)

We need to find how many such permutations occur, given how many times a node has been visited in Gritukan’s scheme.

Graphically looking, any permutation would result in a bunch of different sized isolated cycles. Talking about just one cycle having `p`

nodes, obviously each node of that cycle will occur `p`

times in Gritukan’s scheme (once for each time the algorithm starts for every node). Hence, if `A*=p`

, that means node `i`

is a part of a cycle of size `p`

. Now, keeping that in mind, let us prove one fact that for a valid permutation to occur, in the array A, `p`

will occur `k*p`

times where `k`

is any arbitrary positive integer(otherwise, there will always be some number of nodes less than `p`

left that cannot be satisfied). Hence, for a valid permutation to occur, the only condition is each number `p`

present in the array `A`

must be `k*p`

times in the array.

Now, all the concept behind this problem is over. It all comes down to the math: You have to form k_{i} cycles of p_{i} nodes each, such that the total number of times p_{i} occurs, m_{i}=k_{i}.p_{i}. This can be given by the formula:

\prod \frac{\left(^{m_i}C_{p_i}.\left(p_i-1\right)\right).\left(^{m_i-p_i}C_{p_i}.\left(p_i-1\right)\right).\left(^{m_i-2p_i}C_{p_i}.\left(p_i-1\right)\right)...\left(^{p_i}C_{p_i}.\left(p_i-1\right)\right)}{k_i!} where ^{n}C_{r} means \frac{n!}{r!.(n-r)!}.

We select `p`

nodes from `m`

nodes in ^{m}C_{p} ways, arrange them in a cycle by `p-1`

ways, then repeat it again, until all nodes are put in a cycle. At last we divide by k!, because each cycle is identical.

For my solution, I have broken down the formula to this:

\prod \frac{1}{k_i!}.\frac{1}{p_i^{k_i}}.\left( \frac{p_i!}{0!}.\frac{2p_i!}{i!}.\frac{3p_i!}{2i!}...\frac{m_i!}{m_i-p_i!} \right)

**Complexity and Implementation:** Computation of how many times each number comes in array `A`

can be done in linear time. Then, we iterate over each p_{i} and get m_{i}. Then, loop through m_{i} to p_{i} at a decrement of p_{i}, and calculate the answer. Although nested loop, the complexity of this actually of the order O(N). Since, at max, we will have to iterate from m_{i} to 1, at decrement 1. However, the sum of m_{i} over `A`

is actually `N`

.

We will be actually computing the value of all the factorials%MOD beforehand, along with their inverses, for constant time access. This build operation will take at most 10^{6} operations.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.