We can rephrased the problem as follows

There is a sequence \(A\) . Initially, \(A = (1)\).

Repeat the following operation \(N-1\) times. Let the size of \(|A|\) be \(n\) and \(P\) = \(p/100\).

• With probability \(P\), append (\(\max_{i=1}^{n} A_i)+1\) to \(A\).
• With probability \(1-P\), pick \(i\) between \(1\) and \(n\) uniformly at random and append \(A_i\) to \(A\).

For any sequence of operations we can create a labeled rooted forest of \(N\) nodes. Specifically start with a tree with only node \(1\), in the \(j\)-th operation:

• If operation 1 is performed, add node \(j+1\) as a root to the forest.
• If operation 2 is performed and \(A_i\) is chosen, add an edge between node \(i\) and node \(j\), i,e set \(\text{parent}(j) = i\).

There is a bijection between every possible sequence of \(N-1\) operations and all labeled rooted forest of size \(N\) where \(\text{parent}(v) < v\) for all \(v\).

For a forest \(T\) with rooted trees \(T_1,T_2,\ldots,T_k\) sorted by root labels in increasing order, the number of occurrences of \(i\) in \(A\) = \(|T_i|\), where \(A\) is generated with the same sequence of operations that generated \(T\).

Now we can work on the labeled rooted forest equivalent of the original problem, we want to compute the expected size of the \(k\)-th tree in a random forest generated by the method described above for each \(1 \leq k \leq n\). Note by \(k\)-th tree, I am referring to the tree with the \(k\)-th smallest root label.

Let \(Q = 1-P\).

Let \(p(i,j)\) be the probability that \(i\) is an ancestor of \(j\).

Let \(f(i)\) be the expected size of a tree rooted at node \(i\), We can compute \(f\) by summing the probability of \(i\) being an ancestor for every node thus \(f(i) = \sum_{j\geq i} p(i,j)\).

To compute \(p(i,j)\), look at any tree path \(p = (p_1,p_2,\ldots, p_m)\) with \(p_1 < p_2 < \ldots < p_m\) that starts from \(i\) and ends at \(j\). The probability that this path occurs in the forest is \(\prod_{k>1} \frac{Q}{p_k-1}\) because the probability that \(p_{k-1}\) is a parent of \(p_{k}\) is \(\frac{Q}{p_k-1}\).

\(p(i,j)\) is the sum of probabilities of all such paths which yields

\[ p(i,j) = \frac{Q}{j-1}\prod_{k=i+1}^{j-1} (1+\frac{Q}{k-1}) \]

.

which leads to

\[ f(i) =\prod_{k=i+1}^{N} (1+\frac{Q}{k-1}) \]

.

Once we have \(f(i)\), we can compute the expected size of the \(k\)-th tree as follows:

• \(\text{ans}(1) = f(1)\), since node \(1\) is always a root.
• For \(k>1\), we have:

\[ \text{ans(k)} = \sum_{i=k+1}^n \binom{i-2}{k-2} f(i) P^{k-1} Q^{i-k} \]

If node \(i\) is to be a root of the \(k\)-th tree then there needs to be \(k-1\) roots chosen before \(i\) which yields the \(\binom{i-2}{k-2} P^{k-1} Q^{i-k}\) term.

\(f(i)\) can be computed with suffix product in \(O(n)\) time but this is still a \(O(n^2)\) solution. We can optimize with NTT by splitting apart the binomial term and rewriting the equation as follows

\[ \text{ans(k)} =\frac{P^{k-1}}{(k-2)!} \sum_{i=k+1}^n f(i) (i-2)! * Q^{i-k} \frac{1}{(i-k)!} \]

I won’t go into detail on how to NTT here, you can use the fact \(i + (N-(i-k)) = N+k\) to do the convolution.