Codeforces Round 917 (Div. 2) |
---|
Finished |
You are given a permutation p0,p1,…,pn−1 of odd integers from 1 to 2n−1 and a permutation q0,q1,…,qk−1 of integers from 0 to k−1.
An array a0,a1,…,ank−1 of length nk is defined as follows:
For example, if p=[3,5,1] and q=[0,1], then a=[3,6,5,10,1,2].
Note that all arrays in the statement are zero-indexed. Note that each element of the array a is uniquely determined.
Find the number of inversions in the array a. Since this number can be very large, you should find only its remainder modulo 998244353.
An inversion in array a is a pair (i,j) (0≤i<j<nk) such that ai>aj.
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n and k (1≤n,k≤2⋅105) — the lengths of arrays p and q.
The second line of each test case contains n distinct integers p0,p1,…,pn−1 (1≤pi≤2n−1, pi is odd) — the array p.
The third line of each test case contains k distinct integers q0,q1,…,qk−1 (0≤qi<k) — the array q.
It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅105 and the sum of k over all test cases doesn't exceed 2⋅105.
For each test case, output one integer: the number of inversions in array a modulo 998244353.
43 23 5 10 13 41 3 53 2 0 11 510 1 2 3 48 35 1 7 11 15 3 9 132 0 1
9 25 0 104
In the first test case, array a is equal to [3,6,5,10,1,2]. There are 9 inversions in it: (0,4), (0,5), (1,2), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5). Note that these are pairs (i,j) such that i<j and ai>aj.
In the second test case, array a is equal to [8,4,1,2,24,12,3,6,40,20,5,10]. There are 25 inversions in it.
In the third test case, array a is equal to [1,2,4,8,16]. There are no inversions in it.
Name |
---|