PROBLEM LINK:Author: Denis Anishchenko 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 Explanation: Let's clear up the problem statement given on the contest page. Gritukan writes a permutation
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 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_i1\right)\right).\left(^{m_ip_i}C_{p_i}.\left(p_i1\right)\right).\left(^{m_i2p_i}C_{p_i}.\left(p_i1\right)\right)...\left(^{p_i}C_{p_i}.\left(p_i1\right)\right)}{k_i!}$ where ^{n}C_{r} means $\frac{n!}{r!.(nr)!}$. We select 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_ip_i!} \right)$ Complexity and Implementation: Computation of how many times each number comes in array 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.
This question is marked "community wiki".
asked 11 May '18, 06:34

A few corrections: This is because we can select $p$ nodes from $m$ nodes in $\binom{m}{p}$ ways and arrange them in a cycle in $(p1)!$ ways rather than $(p  1)$ ways. 2 . A minor typo in the following line as well: Sorry for bumping such an old post but I thought that these typos could cause serious troubles for a beginner trying to comprehend the formulas. answered 14 Jun '18, 17:38

Hi , Can you please offer a simpler explanation. With an example. from "Hence, if A[i]=p, that means node i is a part of a cycle of size p." this line onwards. answered 27 May '18, 13:05
