codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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}$.