2223B.md (3625B)
1 Source: https://codeforces.com/problemset/problem/2223/B 2 3 B. Zhily and Barknights 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Zhily developed a game called Barknights, and she is preparing to release a major update on March $25$. Specifically, she plans to add a Module to each Operator in the game, multiplying their power level by the Module's power. 22 23 After the update is released, the famous game streamer Jily will evaluate the Operators' power levels and rank them in a tier list. Whenever an earlier-released Operator is ranked higher than a later-released Operator, it will cause a wave of drama. 24 25 Unfortunately, Zhily accidentally knocked over a hot water kettle and broke her computer, which caused all the Modules to be randomly rearranged. Now Zhily wants to know the expected number of waves of drama that will be generated, but since she has to move on to the next problem, she has entrusted this task to you. 26 27 You are given two arrays $a$ and $b$ of $n$ positive integers. Let $b'$ be a permutation of array $b$ chosen uniformly at random among all $n!$ possible permutations. Define $ c_i = a_i \cdot b'_i$ for $1\le i \le n$. 28 29 Find the expected number of inversions$^{\text{∗}}$ of array $c$. 30 31 $^{\text{∗}}$An inversion in array $c$ is a pair of indices $(i, j)$ such that $1 \le i \lt j \le n$ and $c_i \gt c_j$. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 36 37 The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the length of the arrays $a$ and $b$. 38 39 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$. 40 41 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the array $b$. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$. 44 45 Output 46 47 For each test case, output the expected number of inversions in $c$ modulo $998\,244\,353$. 48 49 Formally, let $M = 998\,244\,353$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$. 50 51 Example 52 53 Input 54 55 ``` 56 3 57 58 5 59 60 1 14 5 1 4 61 62 1 1 1 1 1 63 64 3 65 66 3 2 5 67 68 3 2 5 69 70 10 71 72 10 72 65 43 73 23 78 13 49 99 73 74 31 90 45 19 44 18 59 31 48 29 75 ``` 76 77 Output 78 79 ``` 80 5 81 82 665496236 83 84 820778710 85 ``` 86 87 Note 88 89 In the first test case, since all elements of $b$ are $1$, any of the $5!$ permutations results in $b' = (1, 1, 1, 1, 1)$. Thus, $c = (1, 14, 5, 1, 4)$ is always constant. The inversions are $(2, 3), (2, 4), (2, 5), (3, 4),$ and $(3, 5)$. The expected number of inversions is $5 \equiv 5 \pmod{998\,244\,353}$. 90 91 In the second test case, there are $3! = 6$ equally likely permutations $b'$. The resulting arrays $c$ and their respective inversion counts are shown below: 92 93 | | | | 94 | --- | --- | --- | 95 | $b'$ | $c = (3b'_1, 2b'_2, 5b'_3)$ | Inversion Count | 96 | $(3, 2, 5)$ | $(9, 4, 25)$ | 1 | 97 | $(3, 5, 2)$ | $(9, 10, 10)$ | 0 | 98 | $(2, 3, 5)$ | $(6, 6, 25)$ | 0 | 99 | $(2, 5, 3)$ | $(6, 10, 15)$ | 0 | 100 | $(5, 3, 2)$ | $(15, 6, 10)$ | 2 | 101 | $(5, 2, 3)$ | $(15, 4, 15)$ | 1 | 102 103 The expected number of inversions is $\frac{1+0+0+0+2+1}{6} = \frac{4}{6} = \frac{2}{3}$. 104 105 Modulo $998\,244\,353$, the answer is $2 \cdot 3^{-1} \equiv 665\,496\,236 \pmod{998\,244\,353}$.