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 in$ 和 $0\le jk$，
$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 ijnk$ 且 $a_ia_j$。
定义长度为 $nk$ 的数组 $a_0,a_1,\ldots,a_{nk-1}$ 为：
对所有 $0\le in$ 和 $0\le jk$，
$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 ijnk$ 且 $a_ia_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_ik$），且 $q$ 是 $0\sim k-1$ 的一个排列
输出格式
对每个测试用例输出一行：数组 $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]$
逆序对就是找所有 $(i,j)$（$ij$）且 $a_ia_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$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？