If you are referring to Xmascon 2022, no they are completely different.

Recently I copied Gauss from our library. It was much slower than expected. It was taking modulo as an argument and I was initially passing 1e9+7 there. When I hardcoded it, it sped up 5 times!!! I was expecting some speedup indeed, but definitely not by such a huge factor

Here's my solution:

Instead of considering permutations of size $$$2^n-1$$$, consider $$$2^n-1$$$ random real numbers between $$$0$$$ and $$$1$$$. The root doesn't matter at all(you can see that by noticing that, when looking at permutations, it's always $$$1$$$), so we can remove it to solve the problem on $$$2$$$ independent trees.

Let $$$P_i(x)$$$ be the probability that a tree with depth $$$i$$$ is heap-like if the value of node $$$V$$$ is $$$x$$$, up to constant factors(because in the end we'll only care about the ratio of 2 values of this polynomial). We can start with $$$P_{N-B}(x)=x^{2^{N-B}-2}$$$, and then to calculate $$$P_{i+1}(x)$$$ from $$$P_i(x)$$$, if the value of the root of the tree with depth $$$i+1$$$ is equal to $$$u$$$, then the probability that the left subtree is heap-like(up to constant factors) can easily be seen to be $$$u^{2^i-1}$$$, and to find the probability that the right subtree is heap-like, notice that we're just scaling down the problem from $$$0$$$ to $$$1$$$ to from $$$0$$$ to $$$u$$$, so the probability is $$$P_i(\frac{x}{u}) \cdot u^{2^i-2}$$$. So, $$$P_{i+1}(x)=\int_x^1 u^{2^{i+1}-3} \cdot P_i(\frac{x}{u}) du$$$. Notice that all nonzero coefficients of all $$$P_i(x)$$$ will be in positions $$$x^{2^j-2}$$$ for some natural number $$$j \leq i$$$, so we can calculate all nonzero coefficients of the polynomial $$$P_{i+1}$$$ from the nonzero coefficients of the polynomial $$$P_i$$$ in $$$O(i)$$$, which allows us to calculate all nonzero coefficients of $$$P_{N-1}$$$ in $$$O(N^2)$$$.

Similarly, let $$$Q_i(x)$$$ be the probability that a tree with depth $$$i$$$ is heap-like if the value of node $$$U$$$ is $$$x$$$. We can calculate $$$Q_{N-1}$$$ in the same way as $$$P_{N-1}$$$. Now, the answer is $$$\frac{\int_0^1 P_{N-1}(x) \cdot (\int_0^x Q_{N-1}(y) dy) dx}{\int_0^1 P_{N-1}(x) \cdot (\int_0^1 Q_{N-1}(y) dy) dx}$$$. The numerator can be calculated in $$$O(N^2$$$ $$$log$$$ $$$MOD)$$$, while the denominator can be calculated in $$$O(N$$$ $$$log$$$ $$$MOD)$$$.

  My solution is here.

  The first question we concerned about is how to generate a heap "step by step"? Given a heap-like permutation, let's enumerate the value from $$$1$$$ to $$$n$$$, push its occuring position into a queue, and we can get a BFS order of this heap. With this observation we can turn the original problem into this:

  Find the probability that $$$U$$$ occurs in a random BFS queue before $$$V$$$.

  It's easy to find that $$$U$$$ is on the left-most chain while $$$V$$$ is on the right-most chain of the heap. When performing BFS, we only concerned about how far we've step on these two chains. So, a ideal DP state appears: $$$f(u,v)$$$ representing the probability that the event "$$$u$$$ (on the left-most chain) occurs and $$$v$$$ (on the right-most chain) occurs, but $$$2u,2v+1$$$ don't" happens. Transformation is also apparent, $$$f(2u,v)\overset{+}{\longleftarrow}pf(u,v)$$$ and $$$f(u,2v+1)\overset{+}{\longleftarrow}(1-p)f(u,v)$$$, where $$$p$$$ is the probability that "when $$$u,v$$$ occur in a queue but $$$2u,2v+1$$$ don't, $$$2u$$$ occurs first during the subsequent BFS processing".

  Our last task is to find $$$p$$$. We can get hint from sample 2, guessing $$$p=\frac{s_{2u}}{s_{2u}+s_{2v+1}}$$$, where $$$s_x$$$ is the size of subtree rooted at $$$x$$$.

  Here is a proof. Let $$$S$$$ be the node set of subtree rooted at $$$2u$$$ and $$$T$$$ be the node set of subtree rooted at $$$2v+1$$$. $$$S\cup T$$$ is generated from $$${1,2,\cdots,n}$$$ in some way but we don't care it. What we care about is that known $$$S\cup T=U$$$, how to generate $$$S$$$ and $$$T$$$. Since two subtrees can't affect each other, we can simply choose $$$|S|$$$ elements from $$$U$$$ as $$$S$$$, and $$$T=U\setminus S$$$. But what it means? We know that $$$p_{2u}=\min S$$$ and $$$p_{2v+1}=\min T$$$, so the key is where $$$x=\min U$$$ goes! That is to say, when $$$x\in S$$$, $$$2u$$$ occurs first; when $$$x\in T$$$ otherwise, $$$2v+1$$$ goess first. What's the probability that a particular element is chosen into $$$S$$$? $$$\frac{|S|}{|S|+|T|}$$$ of course, that is the answer.

  With $$$f(u,v)$$$, answer can be calculated by enumerate the situation $$$u\gets U$$$, $$$v\gets{\text{some node upper than }V}$$$. The calculation can be done in $$$\mathcal O(n^2\log P)$$$ or $$$\mathcal O(n^2)$$$.

  Submission: https://atcoder.jp/contests/agc060/submissions/37547686

Let $$$a = \lbrace a_1 \dots a_{|a|} \rbrace \pod{a_i \in [n - 1]}$$$, then $$$f(a) = n! (a_1 - 0)!^{-1} (a_2 - a_1)!^{-1} \dots (n - a_{|a|})!^{-1}$$$.

Consider a directed graph with $$$n + 1$$$ vertices; the value of edge $$$u \to v$$$ is $$$(v - u)!^{-1} \pod{u < v}$$$. The value of a path is defined as the product of value of the edges of the path. Let $$$g(n)$$$ be the sum of value of all paths from $$$0$$$ to $$$n$$$.

Consider $$$a$$$ as a path from $$$0$$$ to $$$n$$$, then we have that $$$f(a)$$$ is equal to the value of path $$$a$$$ multiplied by $$$n!$$$. And $$$\sum_{c \subset a} f(a)$$$ is the sum of the value of all paths that contain the vertices in $$$c$$$, also multiplied by $$$n!$$$. We can divide a path into several parts ($$$0 \to c_1 \to \dots \to c_{|c|} \to n$$$). Then $$$\sum_{c \subset a} f(a) = n! \cdot g(c_1 - 0) g(c_2 - c_1) \dots g(n - c_{|c|})$$$.

I also couldn't get it for a long time. The problem I had was that you can do inclusion-exclusion over sets where you do put the $$$<$$$ signs into and then the solution is pretty much the same except at the end you need to sum over all possible "merges" of a sequence(like for [2,3,1] you sum over [2,3,1], [5,1], [2,4], [6]) which looks unsolvable.

Had to read the beginning carefully again to understand it.