Swaps
Contest: Pinely Round 2 (Div. 1 + Div. 2)
Difficulty rating: 2800
Tags: combinatorics, dp, graphs, math

You are given an array of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). You can perform the following operation several (possibly, zero) times:

- pick an arbitrary $$$i$$$ and perform swap$$$(a_i, a_{a_i})$$$.

How many distinct arrays is it possible to attain? Output the answer modulo $$$(10^9 + 7)$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$).

Output format:
Output the number of attainable arrays modulo $$$(10^9 + 7)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the initial array is $$$[1, 1, 2]$$$. If we perform the operation with $$$i = 3$$$, we swap $$$a_3$$$ and $$$a_2$$$, obtaining $$$[1, 2, 1]$$$. One can show that there are no other attainable arrays.

In the second example, the four attainable arrays are $$$[2, 1, 4, 3]$$$, $$$[1, 2, 4, 3]$$$, $$$[1, 2, 3, 4]$$$, $$$[2, 1, 3, 4]$$$. One can show that there are no other attainable arrays.

Example input:
3
1 1 2

Example output:
2

Example input:
4
2 1 4 3

Example output:
4

Editorial:
Consider a directed graph with $$$n$$$ vertices, where for each vertex $$$i$$$ there is an edge $$$i\to a_i$$$. This is a functional graph, that is, every vertex has exactly one edge outgoing from it. Let's see how our operations affect the graph.
We will write $$$u\to v$$$ to illustrate the fact that $$$a_u = v$$$. Call the operation $$$\mathrm{swap}(a_i, a_{a_i})$$$ picking vertex $$$i$$$. We can assume that we never picked such $$$u$$$ that the operation didn't change the permutation, that is, $$$u\to v\to v$$$.
We will mark some edges in the graph as bold. Initially no edge is bold. When we pick vertex $$$v$$$, one of the following can happen:
• If no bold edges pass into $$$v$$$, go along the bold edges until we can. Let's say the vertex we reached is $$$u$$$. Then mark the edge from $$$u$$$ bold.
• If $$$v$$$ has an incoming bold edge, do nothing.
At every moment of time, the graph corresponds to the permutation in the following way: if $$$v$$$ has an incoming bold edge then $$$a_v = v$$$, otherwise, if $$$u$$$ is the vertex we reach by going from $$$v$$$ along the bold edges, and $$$u\to w$$$, then $$$a_v = w$$$. Also, one can see that according to the algorithm of making edges bold no vertex ever has more than one incoming bold edge.
It is clear that each valid subset of bold edges corresponds to a unique permutation. However, one can see that the same permutation can correspond to multiple subsets. In particular, for a component of the graph, if $$$a_v = v$$$ for all vertices of the cycle in this component, then the boldness of all edges outside the cycle is uniquely determined, but for the edges of the cycle any subset of these edges that doesn't include exactly one of them corresponds to this permutation. To avoid this uncertainty, we say that this permutation will correspond to the subset of bold edges where all the edges from the cycle are bold (this is an invalid subset, because there is no sequence of operations that would mark it bold).
Now we want to calculate the number of possible subsets of bold edges. Each vertex can have either no incoming bold edges (there is $$$1$$$ way to do this) or any one of them can be bold ($$$\mathrm{in}_v$$$ ways to do this for vertex $$$v$$$). So the answer could be just $$$\prod_{v}(\mathrm{in}_v + 1)$$$. However, since some of the configurations are invalid, we need to modify the answer.
In particular, consider any cycle $$$c_1\to\ldots\to c_k\to c_1$$$. All excluded subsets of edges correspond to exactly one of $$$c_{i+1}$$$ having either no bold edge incoming, or any edge except $$$c_i\to c_{i+1}$$$. Therefore, the number of ways to choose the bold edges among the ones incoming to this cycle is
$$$$$$\prod_{i=1}^k(\mathrm{in}_{c_i} + 1) - \sum_{i=1}^k\mathrm{in}_{c_i}.$$$$$$
Thus, the final answer is
$$$$$$\prod_{\text{cycles}}\left(\prod_{i=1}^k(\mathrm{in}_{c_i} + 1) - \sum_{i=1}^k\mathrm{in}_{c_i}\right)\cdot\prod_{\text{other }v}(\mathrm{in}_v + 1).$$$$$$