CF1917D Yet Another Inversions Problem

给定一个长度为 $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]$。 注意，题目中的所有数组均为从零开始编号。并且数组 $a$ 的每个元素都是唯一确定的。 请你计算数组 $a$ 中的逆序对数量。由于答案可能很大，只需输出其对 $998\,244\,353$ 取模的结果。 数组 $a$ 中的逆序对定义为一对下标 $(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$），分别表示数组 $p$ 和 $q$ 的长度。 每个测试用例的第二行包含 $n$ 个两两不同的整数 $p_0, p_1, \ldots, p_{n-1}$（$1 \le p_i \le 2n-1$，且 $p_i$ 为奇数），表示数组 $p$。 每个测试用例的第三行包含 $k$ 个两两不同的整数 $q_0, q_1, \ldots, q_{k-1}$（$0 \le q_i < k$），表示数组 $q$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$k$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示数组 $a$ 中逆序对的数量对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，数组 $a$ 为 $[3, 6, 5, 10, 1, 2]$。其中有 $9$ 个逆序对，分别为 $(0, 4)$、$(0, 5)$、$(1, 2)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$、$(3, 5)$。这些都是满足 $i < j$ 且 $a_i > a_j$ 的下标对。 在第二个测试用例中，数组 $a$ 为 $[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$。其中有 $25$ 个逆序对。 在第三个测试用例中，数组 $a$ 为 $[1, 2, 4, 8, 16]$。其中没有逆序对。 由 ChatGPT 4.1 翻译