Let \(a_n(y)\) be the expected value of the output of the following procedure for a real number \(y\) (\(0 \leq y \leq 1\)) and a non-negative integer \(n\).

• Generate \(n\) real numbers within \([0,1]\), and let them be \(x_1, \cdots, x_n\). If \(x_1 < \cdots < x_n < y\) is not satisfied, output \(0\) and terminate. If \(x\) is in ascending order, output \(\prod_{1 \leq i \leq n} (y^A + \sum_{i < j \leq n} x_j^A)\) and terminate.

Let \(f(y,x) = \sum_{0 \leq n} a_n(y)x^n\). As we will see later, \(a_n(y)\) is a polynomial of \(y\), and \(f\) can be defined as a formal power series in two variables. For now, we proceed by defining \(f\) as the formal sum above. Ultimately, we want to find \(N! [x^N]f(1,x)\).

Consider the procedure of choosing one term from \(y^A, x_{i+1}^A, \cdots x_N^A\) for each \(i\) and calculating their product. If \(x_j^A\) is chosen for some \(i\), we draw an arrow from \(i\) to \(j\). If \(y^A\) is chosen, we draw an arrow from \(i\) to *, where * is a vertex prepared arbitrarily. This forms a tree.

By considering this tree, we can derive the equation that \(f\) satisfies. We decompose the problem into subproblems for each subtree of the direct children of *. Consider the “weight” of a subtree rooted at a child \(v\). Given that the real number \(t\) corresponding to vertex \(v\) ranges within \(0 \leq t \leq y\), the weight of this subtree is

\(y^A x \int_{0 \leq t \leq y} f(t,x) dt\).

Here, \(y^A\) is the weight of the edge \(v \to *\), and \(x\) is the term for counting \(v\) as a vertex.

If * has \(k\) children, we first order the subtrees to calculate, and then multiply by a coefficient of \(1/k!\). Consequently, we find that \(f\) satisfies the following equation:

\(f(y,x) = \exp(y^A x \int_{0 \leq t \leq y} f(t,x) dt)\).

From this, \(a_n(y)\) can be determined in the order of \(n=0,1,\cdots\), and it is found to be a polynomial of \(y\).

Upon further observation, \(a_n(y)\) is found to be a constant multiple of \(y^{(A+1)n}\).

Therefore, if we let \(z = y^{A+1}x\), we can write \(g(z) = f(x,y)\) using some formal power series \(g(z) = \sum_{0 \leq n} b_n z^n\). Rewriting the equation for \(f\) obtained above in terms of \(g\),

\(g(z) = \exp(\sum_{0 \leq n} \frac{b_n}{(A+1)n+1} z^{n+1})\).

Let \(h(z)\) be the expression inside the \(\exp\).

Knowing \([z^n] g\) allows us to determine \([z^{n+1}] h(z)\), which in turn allows us to calculate \([z^{n+1}] g(z)\), thus letting us find the coefficients of \(g\) in ascending order. The most intuitive method is to calculate \(\exp\) \(N\) times, but this results in a time complexity of \(O(N^2 \log N)\), which does not meet the time limit.

Thus, we use a slightly smarter method to calculate \([z^{n+1}] g(z)\). Considering the coefficient of \([z^n]\) in \(\frac{d}{dz}g = \frac{d}{dz}\exp(h) = \frac{d}{dz}h \times \exp(h) = \frac{d}{dz}h \times g\), the calculation of \([z^{n+1}] g(z)\) can be done in \(O(n)\).

Thus, this problem can be solved in \(O(N^2)\) time overall.

Sample Solution (C++)