A6901. 另一个逆序对问题
编程题
提高+/省选-
知识点
题目描述
给定一个长度为 $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$。
定义长度为 $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$。
每个测试用例：
- 第一行两个整数 $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
9 25 0 104
说明/提示
## 样例解释
### 样例 1
输入里：
$p=[3,5,1]$，$q=[0,1]$，所以 $2^{q}=[2^0,2^1]=[1,2]$。
按定义 $a_{i\cdot k+j}=p_i\cdot 2^{q_j}$（这里 $k=2$）：
- $i=0$：得到 $[3\cdot1,\,3\cdot2]=[3,6]$
- $i=1$：得到 $[5\cdot1,\,5\cdot2]=[5,10]$
- $i=2$：得到 $[1\cdot1,\,1\cdot2]=[1,2]$
所以 $a=[3,6,5,10,1,2]$。
逆序对就是找所有 $(i,j)$（$i<j$）且 $a_i>a_j$ 的对，数一数共有 $9$ 个，所以输出 $9$。
### 样例 2
题目给出的第二组数据生成的数组是：
$a=[8,4,1,2,24,12,3,6,40,20,5,10]$，
其中逆序对个数为 $25$，所以输出 $25$。
### 样例 3
第三组数据里 $p=[1]$，$q=[0,1,2,3,4]$，得到：
$a=[1,2,4,8,16]$，它是从小到大不下降的，因此没有逆序对，输出 $0$。
### 样例 1
输入里：
$p=[3,5,1]$，$q=[0,1]$，所以 $2^{q}=[2^0,2^1]=[1,2]$。
按定义 $a_{i\cdot k+j}=p_i\cdot 2^{q_j}$（这里 $k=2$）：
- $i=0$：得到 $[3\cdot1,\,3\cdot2]=[3,6]$
- $i=1$：得到 $[5\cdot1,\,5\cdot2]=[5,10]$
- $i=2$：得到 $[1\cdot1,\,1\cdot2]=[1,2]$
所以 $a=[3,6,5,10,1,2]$。
逆序对就是找所有 $(i,j)$（$i<j$）且 $a_i>a_j$ 的对，数一数共有 $9$ 个，所以输出 $9$。
### 样例 2
题目给出的第二组数据生成的数组是：
$a=[8,4,1,2,24,12,3,6,40,20,5,10]$，
其中逆序对个数为 $25$，所以输出 $25$。
### 样例 3
第三组数据里 $p=[1]$，$q=[0,1,2,3,4]$，得到：
$a=[1,2,4,8,16]$，它是从小到大不下降的，因此没有逆序对，输出 $0$。