The intended solution is not difficult. The tricky part is rounding off the number.

long double doesn't work. Find out why.

Use long arithmetic.

For each pair $$$(i, j)$$$, the probability of it being an inversion is:
\begin{cases} \displaystyle \frac{r_i — 1}{2 r_j} & \text{if } r_i \leq r_j, \ \displaystyle \frac{2 r_i — r_j — 1}{2 r_i} & \text{if } r_i > r_j. \end{cases}

The answer is the sum of probabilities for all pairs. However, rounding the result is nontrivial because the decimal part of the expected value can be extremely close to $$$0.0000005$$$. Consider next test case:

22
8 10 12 13 15 18 19 20 21 22 23 26 27 28 29 79 82 86 87 88 91 95

The exact answer is $$$53.418336500000000000094\dots$$$ A naive solution gives 53.418336 due to precision error. So we should use long arithmetic. Let's take the denominator as twice the product of the given numbers. Compute the numerator using basic arithmetic operations. After that we should round off $$$\frac{\text{numerator}}{\text{denominator}}$$$. There are many ways to do it. I did it by using large powers of 10.
Code

Solve the problem for $$$n \leq 4$$$.

Did you notice anything when $$$n = 4$$$?

A solution always exists when $$$n \geq 4$$$

Try to solve the problem for $$$n \gt 4$$$ using heuristic algorithm.

At the end, you need to apply your solution for n = 4(only a couple of times).

IOI1989P1

If $$$n \leq 4$$$ just brute-force the problem using bfs.
If $$$n \gt 4$$$:
- Let $$$\text{b_pos}$$$ be the index of the leftmost B in the current string.
- Let $$$\text{a_pos}$$$ be the index of the leftmost A in the substring starting from $$$\text{b_pos} + 2$$$ to $$$2n$$$.
- Swap $$$s[\text{b_pos}, \text{b_pos} + 1]$$$ with $$$s[\text{a_pos}, \text{a_pos} + 1]$$$ using 3 operations.

If $$$\text{a_pos}$$$ cannot be found, apply $$$n=4$$$ solution. Don't forget to handle a corner case when $$$\text{a_pos} = 2 n$$$
Code

Choose the largest available digit at each step.

dp

Think about powers of 10.

Let's say that you know the answer for $$$10^i$$$. How can you find the answer for $$$10^{i + 1}$$$? What about $$$2 \cdot 10^i, 3 \cdot 10^i \dots 9 \cdot 10^i$$$?

What additional information should you store to calculate the answer for these numbers?

3d dp

CF331C3

Let's define $$$\text{pair \lt long long, int \gt } \text{dp}[i][j][k]$$$ where $$$i \lt 18, j \lt 10, k \lt 10$$$.
$$$\text{dp}[i][j][k].\text{first}$$$ represents the number of operations needed to reduce $$$10^{i + 1} - j$$$ to $$$-\text{dp}[i][j][k].\text{second}$$$($$$0 \leq \text{dp}[i][j][k].\text{second} \leq 9$$$).
$$$0 \leq k \leq 9$$$ is the maximum digit allowed in the suffix.
Using this dp we can easily calculate the answer in $$$\mathcal{O} (\log{n})$$$
Code

Solve the problem in $$$\mathcal{O}(n^3)$$$.

Try to optimize solution using inclusion–exclusion principle.

$$$\mathcal{O} (|\Sigma| \cdot n^2)$$$ solution is short and simple, but it's hard to guess it.

CCAMBALLS

Let us define $$$\text{cnt}[i]$$$ as the number of occurrences of the $$$i$$$-th character.The DP state $$$\text{dp}[i][j]$$$ represents the number of strings that can be formed using the first $$$i$$$ characters and partitioned into $$$j$$$ blocks (a block is a sequence of consecutive identical characters). Note that a single string may be counted multiple times in this formulation. Compute $$$\text{dp}[i]$$$ in $$$\mathcal{O}(n^2)$$$ using binomial coefficients. After computing $$$\text{dp}[|\Sigma|]$$$ it's possible to find the total number of strings by using inclusion-exclusion formula. For implementation details, refer to the provided code.

What is necessary requirement?

$$$3 \mid n \cdot m$$$
Without loss of generality let's assume that $$$3 \mid n$$$.

Construct a solution if $$$6 \mid n \cdot m$$$

Consider a case $$$n = 3$$$. What can you say about $$$m$$$?

What if $$$n \cdot m$$$ is odd, $$$n \geq 9$$$ and $$$m \geq 5$$$? Does solution exist for this case? Can you prove it?

Try to construct solution for $$$9 \times 5$$$

Use it to construct a solution for the last case.

CEOI2021B

It's very clear that $$$3 \mid n \cdot m$$$ and $$$\text{min}(n, m) \geq 2$$$. Without loss of generality let's assume that $$$3 \mid n$$$ (otherwise, transpose the grid).
1. For $$$n = 3$$$ and $$$m \geq 2$$$, a solution exists if and only if $$$m$$$ is even. It can be proved by induction.
2. If $$$n$$$ or $$$m$$$ is even, use a tiling pattern with $$$3 \times 2$$$ or $$$2 \times 3$$$ blocks.
3. $$$n \cdot m$$$ is odd, $$$n \geq 9$$$ $$$m \geq 5$$$. There exists a solution for $$$9 \times 5$$$. You can construct it on paper or by using profile dp. Now if you put $$$9 \times 5$$$ in the upper left corner the grid splits into two rectangles: $$$(n - 9) \times 5$$$ and $$$n \times (m - 5)$$$. Solve these using construction of previous case.
Code

Stirling numbers of the first kind

Cayley's formula

The problem is OEIS-able.
The formula is obtained by combining the two given ideas.
Code

Try to think about the problem in terms of graph

Solve the problem when grid is empty.

Try to get rid of cycles of length 2.

Use inclusion–exclusion principle.

For each $$$i$$$, find the number of completion with at least $$$i$$$ cycles of length 2.

Consider a component with $$$ \gt 1$$$ edges. It's impossible to form a cycle of length 2 with vertices of this component.

ARC186A

For an $$$N \times N$$$ grid $$$G$$$, construct a directed bipartite graph with partitions $$${R_1, \dots, R_N}$$$ (rows) and $$${C_1, \dots, C_N}$$$ (columns):
- If $$$G[i][j] = A$$$, direct an edge from $$$R_i$$$ to $$$C_j$$$.
- If $$$G[i][j] = B$$$, direct an edge from $$$C_j$$$ to $$$R_i$$$.

The goal is to count the number of ways to complete this graph into non-intersecting cycles covering all vertices, with no 2-cycles It's easy to see that such cycles can only be formed from isolated vertices or 1-edge components. The answer can be calculated by inclusion–exclusion principle iterating over the number of 2-length cycles formed by isolated vertices, the number of 1-edge components from left part and 1-edge components from right part. Time complexity: $$$\mathcal{O}(N^3)$$$.
Code

How long $$$i$$$-th number has to be be in stack?

Try to represent the problem in terms of sets of segments(endpoints of segments must be unique).

This problem may be useful.

Add only essential edges.

Iterate over the endpoints from left to right

CF1691E
JOISC2017B

$$$p_1, \dots, p_n$$$ is a given permutation.
For each $$$i$$$ let's consider $$$j = \max k \colon p_k \leq p_i $$$. At the $$$j$$$-th iteration we should be able to get $$$p_i$$$. Otherwise, solution doesn't exist. Using that observation we can represent the problem in terms of segments with unique endpoints. Let the segment of the $$$i$$$-th number be equal to $$$[l_i, r_i]$$$. If 2 segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect and neither is contained in the other, we can not move $$$i$$$-th and $$$j$$$-th numbers to the same stack. In that case, let's add an edge between $$$i$$$-th and $$$j$$$-th vertices. If resulting graph is bipartite, a solution exist. The goal is to find a bipartition of the graph. The main idea is to consider only the necessary edges. Let's store components of the graph in DSU. Every leader of a component has all segments of its elements stored in the set. We can merge 2 sets using small-to-large trick. Overall time complexity is $$$\mathcal{O}(n \log^2 n)$$$. Let's iterate over the endpoints from left to right. Assume we are at position $$$x$$$. For each component, store the segment $$$[l_i, r_i]$$$ such that $$$l_i \lt x \lt r_i$$$ and $$$r_i$$$ is minimal. Let's call this segment the representative of the component. All representatives are stored in the set(segments in the set sorted by $$$r_i$$$). There are two cases:
1. $$$x = l_i$$$ for some $$$i$$$. Add edges between the $$$i$$$-th vertex and all representatives $$$[l_j, r_j]$$$ in the set where $$$r_j \lt r_i$$$. Delete these segments and insert the representative of the new merged component.
2. $$$x = r_i$$$ for some $$$i$$$. If $$$[l_i, r_i]$$$ is the representative, erase it from the set and insert a new one from the leader’s set of segments(if possible).
Finally, verify the result by simulating the algorithm described in the problem statement.
Code

Hamilton Paths in Grid Graphs
Code