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 ith node occurs A[i] 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[i], then P[P[i]], 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[i]=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 ki cycles of pi nodes each, such that the total number of times pi occurs, mi=ki.pi. 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 nCr means \frac{n!}{r!.(n-r)!}.
We select p nodes from m nodes in mCp 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 pi and get mi. Then, loop through mi to pi at a decrement of pi, 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 mi to 1, at decrement 1. However, the sum of mi 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 106 operations.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.