A6901 | $另一个逆序对问题$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的排列 $p_0,p_1,\ldots,p_{n-1}$，其中 $p$ 是 $1$ 到 $2n-1$ 之间所有**奇数**的一个排列；以及一个长度为 $k$ 的排列 $q_0,q_1,\ldots,q_{k-1}$，其中 $q$ 是 $0$ 到 $k-1$ 的一个排列。 定义长度为 $nk$ 的数组 $a_0,a_1,\ldots,a_{nk-1}$ 为： 对所有 $0\le i<n$ 和 $0\le j<k$， $a_{i\cdot k+j}=p_i\cdot 2^{q_j}$。 例如，若 $p=[3,5,1]$ 且 $q=[0,1]$，则 $a=[3,6,5,10,1,2]$。 注意：所有数组都从 $0$ 开始编号，并且数组 $a$ 的每个元素都是唯一的。 请你计算数组 $a$ 中的逆序对数量，对 $998244353$ 取模输出。 逆序对定义为一对下标 $(i,j)$，满足 $0\le i<j<nk$ 且 $a_i>a_j$。

第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。 每个测试用例： - 第一行两个整数 $n,k$（$1\le n,k\le 2\cdot 10^5$） - 第二行 $n$ 个两两不同的奇数 $p_0,\ldots,p_{n-1}$（$1\le p_i\le 2n-1$），且 $p$ 是所有奇数的一个排列 - 第三行 $k$ 个两两不同的整数 $q_0,\ldots,q_{k-1}$（$0\le q_i<k$），且 $q$ 是 $0\sim k-1$ 的一个排列 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$，$k$ 的总和不超过 $2\cdot 10^5$。

对每个测试用例输出一行：数组 $a$ 的逆序对数量对 $998244353$ 取模的结果。

输入 #1

4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1

输出 #1

C++ 编辑器

输入

输出