Zhily and Barknights

Observation 1: linearity of expectation saves you from permutation hell

Let

$$X_{ij} = [c_i > c_j] \qquad (i<j),$$

where $[\cdot]$ is the indicator function. Then

$$\mathbb E[\text{inv}(c)] = \sum_{1\le i<j\le n} \mathbb E[X_{ij}] = \sum_{i<j} \Pr(c_i > c_j).$$

So we only need the inversion probability for one fixed pair $(i,j)$.

For fixed $i<j$, the pair $(b'_i,b'_j)$ is uniformly distributed over all ordered pairs of distinct positions $(p,q)$ of the original array $b$. Each such ordered pair appears in exactly $(n-2)!$ permutations, so it’s uniform. Therefore

$$\Pr(c_i > c_j) = \frac{\#\{(p,q): p\ne q,\ a_i b_p > a_j b_q\}}{n(n-1)}.$$

Hence the expected number of inversions is

$$\frac{1}{n(n-1)} \sum_{i<j} \#\{(p,q): p\ne q,\ a_i b_p > a_j b_q\}.$$

If you try to compute that pair-by-pair directly, you get smacked by an extra factor of $n$. So we need a better view.

Observation 2: add the forbidden cases, then subtract them cleanly

Define

$$T = \sum_{i<j}\sum_{p\ne q}[a_i b_p > a_j b_q].$$

The answer is just

$$\frac{T}{n(n-1)}.$$

Now define the easier quantity

$$T' = \sum_{i<j}\sum_{p,q}[a_i b_p > a_j b_q],$$

where we also allow $p=q$.

What did we overcount? Exactly the cases with $p=q$:

$$[a_i b_p > a_j b_p] = [a_i > a_j],$$

because every $b_p$ is positive.

So for each pair $(i,j)$, the fake contribution from $p=q$ is either $n$ or $0$, and globally

$$T = T' - n\cdot \mathrm{inv}(a),$$

where

$$\mathrm{inv}(a)=\#\{(i,j): i<j,\ a_i>a_j\}.$$

That positivity condition is doing real work here. If $b$ had zeros or negatives, life would be much more annoying. Thankfully, the problem is not that evil.

Observation 3: reinterpret $T'$ as a counting problem on $n^2$ numbers

For every index $i$ and every position $p$ of $b$, create one item

$$(v_{i,p}, i), \qquad v_{i,p}=a_i b_p.$$

There are $n^2$ such items.

Then

$$T' = \#\{((i,p),(j,q)) : i<j,\ v_{i,p} > v_{j,q}\}.$$

In words:

• each item has a value $a_i b_p$,
• and a group/index $i$,
• and we want to count pairs of items where the item from the smaller index has the larger value.

That’s suddenly a very standard offline counting problem.

Observation 4: sort by value, use a Fenwick tree on indices

Sort all items by value in descending order.

Suppose we are processing an item from index $j$. Any item already processed has value strictly larger — except for equal values, which must not be counted because the inequality is strict.

So the correct way is:

• process equal values in one batch,
• for each item in the batch, query how many already-processed items have index $<j$,
• after all queries in the batch are done, insert the whole batch into the Fenwick tree.

If the Fenwick tree stores how many processed items came from each index, then for an item from index $j$, its contribution is

$$\text{pref}(j-1),$$

where $\text{pref}(x)$ is the number of processed items with index at most $x$.

Summing this over all items gives exactly $T'$.

Why? Because every counted pair is:

• from an earlier batch $\Rightarrow$ strictly larger value,
• from a smaller index $\Rightarrow$ satisfies $i<j$,
• counted once, at the moment the smaller-valued item is queried.

That’s the whole trick. The problem looks like probability soup, but underneath it’s just an inversion-like count on $n^2$ generated numbers.

Algorithm

For one test case:

1. If $n=1$, answer is $0$.
2. Build the list $$\{(a_i b_p, i) : 1\le i,p\le n\}$$ of size $N=n^2$.
3. Sort it by value descending.
4. Sweep through equal-value blocks:
   • for each item $(v,j)$ in the block, add Fenwick prefix sum up to $j-1$ to $T'$,
   • then insert all indices $j$ from the block into the Fenwick tree.
5. Compute $\mathrm{inv}(a)$.
6. Compute $$T = T' - n\cdot \mathrm{inv}(a).$$
7. Output $$T \cdot (n(n-1))^{-1} \bmod 998244353.$$

Correctness sketch

We prove the algorithm computes the expected number of inversions.

For each pair $i<j$,

$$\Pr(c_i>c_j)=\frac{\sum_{p\ne q}[a_i b_p>a_j b_q]}{n(n-1)}.$$

By linearity of expectation,

$$\mathbb E[\text{inv}(c)] = \frac{1}{n(n-1)} \sum_{i<j}\sum_{p\ne q}[a_i b_p>a_j b_q].$$

So it is enough to compute the integer numerator

$$T=\sum_{i<j}\sum_{p\ne q}[a_i b_p>a_j b_q].$$

Now define

$$T'=\sum_{i<j}\sum_{p,q}[a_i b_p>a_j b_q].$$

The only difference is the $p=q$ terms. Since $b_p>0$,

$$[a_i b_p>a_j b_p]=[a_i>a_j].$$

There are $n$ choices of $p$, hence

$$T=T'-n\cdot \mathrm{inv}(a).$$

Finally, $T'$ equals the number of pairs of items $((i,p),(j,q))$ with $i<j$ and $a_i b_p>a_j b_q$. After sorting all items by decreasing value, an item contributes exactly the number of already processed items coming from smaller indices. Equal values must be processed as a batch so they do not count each other. Therefore the Fenwick sweep computes exactly $T'$.

Thus the algorithm returns the exact expected value modulo $998244353$.

Complexity

Let $N=n^2$.

• Building the items: $O(N)$
• Sorting: $O(N\log N)$
• Fenwick sweep: $O(N\log n)$
• Counting $\mathrm{inv}(a)$: $O(n^2)$

So the total is

$$O(n^2\log n^2)=O(n^2\log n).$$

Memory usage is $O(n^2)$.

Because the sum of $n$ over all test cases is at most $2000$, we have

$$\sum n^2 \le \left(\sum n\right)^2 \le 4\cdot 10^6,$$

so this is easily fine.

Yeah, the intended trick is basically: turn the probability problem into one giant offline inversion count. Once you see that, the rest is just bookkeeping.