In the problem statement, the destination of an edge from vertex \(i\) is \(x_i\), but \(x\) conflicts with variables, so we will write it as \(p_i\). Also, vertices are \(0\)-indexed.

We fix \(N\). Let \(f_{N,K,C}\) be the answer for the number of \(i\) such that \(i<x_i\) being \(K\) and the number of connected components being \(C\), and define a two-variable polynomial \(f_N(x,y)=\sum_{K,C} f_{N,K,C} \ x^K y^C\).

To state the conclusion, \(f_N(x,y)\) can be written in the following closed form:

\(f_N(x,y)=\sum_{0 \leq k \leq N-1} C(N-1,k) (\prod_{0 \leq i<k} ((N-i)x+i)) (\prod_{0 \leq i<N-k} (i+y))\)

Here, \(C(a,b)\) represents “\(a\) choose \(b\)”. For each \(k\), we need to compute \([x^K]\prod_{0 \leq i<k} ((N-i)x+i)\) and \([y^C]\prod_{0 \leq i<N-k} (i+y)\). This can be computed using divide-and-conquer + FFT, with an overall time complexity of \(O(N \log^2N)\).

Below, we prove the closed form of \(f_N(x,y)\).

First, let us find the answer for \(C=1\): \(g_N(x)=[y^1]f_N(x,y)\). The answer is:

\(g_N(x)=\sum_{0 \leq k \leq N-1} (N-1)!/k! (\prod_{0 \leq i<k} ((N-i)x+i))\)

Proof of the formula for \(g_N(x)\): The above formula can be interpreted as counting the following objects:

• Prepare a graph with \(N\) vertices and fix some \(k\) as a special vertex. Each vertex other than \(k\) extends exactly one edge. For vertex \(i\) (\(i<k\)), the edge from there can be chosen freely. For vertex \(i\) (\(i>k\)), it extends an edge to a vertex with a smaller index. Define the \(K\)-value of this graph as the number of \(i\) satisfying \(i \leq p_i\). (Note that this includes \(i=p_i\).)

Let \(A_k\) be the set of objects corresponding to some \(k\). \(A_k\) has a one-to-one correspondence with the following set \(B_k\):

• Connected functional graphs where the maximum number of vertices \(i\) satisfying either of the following conditions is \(k\):
  • (i) \(i\) is contained in a cycle.
  • (ii) \(i<p_i\).

We can confirm that \(k\) cannot satisfy both conditions simultaneously. Define the \(K\)-value of this graph as the number of \(i\) satisfying \(i <p_i\). (This time, \(i=p_i\) is not included.)

There exists a bijection between \(A_k\) and \(B_k\), specifically a bijection that preserves the \(K\)-value.

Details of the bijection

Take one graph in $A_k$ and call it $G$. Let the cycles of $G$ be $S_1,S_2,\cdots,S_l$. Each cycle $S_i$ is a sequence of vertex numbers arranged so that the vertex with the smallest index comes at the end. Furthermore, we decide the order of cycles in ascending order of the vertex numbers at the end. Define sequence $Z$ as $Z=S_1+S_2+\cdots+S_l$ and express it as $Z=(Z_1,Z_2,\cdots,Z_m)$.
First, delete all edges within cycles. We consider cases based on whether there exists a vertex $Z_i$ in $Z$ such that $k < Z_i$.
(i) If it does not exist: Reconnect sequence $Z'=Z+(k)$ as a cycle. The graph obtained this way corresponds to a case (i) graph in set $B_k$.
(ii) If it exists: Let $c$ be the minimum $i$ satisfying $k< Z_i$, and let $L=(Z_1,\cdots,Z_{c-1})$, $R=(Z_{c},\cdots,Z_m)$. Let the head of $L$, tail of $L$, and tail of $R$ be $x$, $y$, and $z$, respectively. First, create edges $k \to R_1 \to R_2 \to \cdots \to z$. Furthermore, by creating edges as shown below, we can obtain a case (ii) graph in $B_k$.
(ii-1) When $z<\min(x,y)$ or $\max(x,y)< z$: Create a cycle $z \to x \to L_2 \to \cdots \to y \to z$.
(ii-2) When $y< z< x$: Let $d$ be the maximum $i$ satisfying $z < L_i$. Create a cycle $x \to L_2 \to \cdots \to L_d \to z \to L_{d+1} \to \cdots \to y \to x$.
(ii-3) When $x< z< y$: Let $d$ be the maximum $i$ satisfying $z > L_i$. Create a cycle $x \to L_2 \to \cdots \to L_d \to z \to L_{d+1} \to \cdots \to y \to x$.
Through careful discussion, it can be confirmed that the $K$-value is preserved by the above operations and that reverse operations are possible.

Now we solve for general \(C\).

Suddenly, let us consider rooted trees satisfying the following conditions:

• Number of vertices is \(N\).
• Root is \(k\).
• The parent of vertex \(i>k\) is \(i-1\).

Define the \(K\)-value of this tree as the number of \(i\) satisfying \(i<p_i\). Let \(T_k(x)\) be the polynomial obtained by multiplying \(x^K\) for all rooted trees and summing them up, and consider the problem of finding this.

As a conclusion, \(T_k(x)\) can be calculated with the following formula:

\(T_k(x)=(\prod_{0 \leq i<k} ((N-i)x+i)) \times (N-k) / N\)

Proof: We show that \(T_k(x) \times N =\left(\prod_{0 \leq i<k} ((N-i)x+i)\right) \times (N-k)\). That is, we create a bijection between (rooted trees with one additional vertex marked) and the “something” counted by the right-hand side. The “something” is a set of functional graphs (but only \(k\) has out-degree \(0\)) satisfying the following conditions:

• Choose one \(i\) satisfying \(k \leq i < N\) and call the vertex \(w\).
• Vertex \(k\) does not extend an edge.
• The destination of vertex \(i\) (\(i>k\)) is \(i-1\).
• The destination \(p_i\) of vertex \(i\) (\(i<k\)) can be chosen freely.
• Define the \(k\)-value of this graph as the number of \(i\) satisfying \(i \leq p_i\). (Note that this includes \(i=p_i\))
• Note that this graph is not necessarily connected.

Now, suppose there was a graph \(G\) satisfying the above conditions. \(G\) has the form of a tree rooted at \(k\) and functional graphs arranged side by side. Let the cycles of the functional graphs be \(S_1,S_2,\cdots,S_l\). Each cycle \(S_i\) is a sequence of vertex numbers arranged so that the vertex with the smallest index comes at the end. Furthermore, we decide the order of cycles in ascending order of the vertex numbers at the end. Define sequence \(Z\) as \(Z=S_1+S_2+\cdots+S_l\) and express it as \(Z=(Z_1,Z_2,\cdots,Z_m)\).

We transform \(G\) to correspond to an element of \(T_k(x) \times N\). First, delete all edges within cycles. Next, create a cycle \(Z_1 \to Z_2 \to \cdots \to Z_m \to w \to Z_1\). Finally, mark vertex \(Z_1\). This becomes a rooted tree with one additional vertex marked.

Through careful discussion, it can be confirmed that the \(K\)-value is preserved by the above operations and that reverse operations are possible.

Rewriting \(g_N(x)\) using \(T_k(x)\):

\(g_N(x)=\sum_{0 \leq k \leq N-1} T_k(x) \times C(N,k) \times (N-k-1)!\)

This can be interpreted as counting rooted trees with the following properties:

• First, color the \(N\) vertices red and blue. Let the number of red vertices be \(k\). Let the indices of red vertices be \(r_1,\cdots,r_k\) and the indices of blue vertices be \(b_1,\cdots,b_{N-k}\). Create a rooted tree with vertex \(b_1\) as the root. For each red vertex, its parent can be chosen freely. For each blue vertex \(b_i\), its parent is chosen from \(b_1,\cdots,b_{i-1}\). The \(K\)-value of this tree is the number of edges \(r_i \to r_j\) (\(i<j\)) + the number of red \(\to\) blue edges.

Let us count arrangements of \(C\) of these rooted trees. First, color the \(N\) vertices red and blue. Then, create a rooted forest with exactly \(C\) components using only blue vertices. Finally, we need to decide the destinations of edges from red vertices. There are exactly \(T_k(x)\) ways for this.

Summarizing the above:

\(f_N(x,y)=\sum_{0 \leq k \leq N-1} C(N,k) \times T_k(x) \times (\prod_{0 \leq i<N-k} (i+y))\)

Expanding \(T_k(x)\):

\(f_N(x,y)=\sum_{0\leq k\leq N-1} C(N-1,k) (\prod_{0 \leq i<k} ((N-i)x+i)) (\prod_{0 \leq i<N-k} (i+y))\)

This gives us the initial formula. This completes the proof.

Writer’s solution (C++)