分数: 1200 点
问题陈述
你有两个长度-N 非负整数序列: A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N).
对于排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N),定义成本 P as \sum_{i=1}^{N} \left \lfloor \frac{A_{P_i}}{2^{B_i}} \right \rfloor.
求模数 998244353,排列 P 实现成本最低。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 0 \le B_i \le 30
- 总和 一个输入文件中的 N 所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N A_1\ A_2\ \dots\ A_N B_1\ B_2\ \dots\ B_N
输出
输出 T 行。的 i第行 (1 \le i \le T) 应包含以下问题的答案 \mathrm{case}_i.
示例输入 1
7 2 5 9 0 1 3 3 4 10 0 1 2 4 1 2 3 4 0 0 1 1 5 1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0 11 19 68 97 62 99 52 57 19 43 80 96 5 3 3 2 3 4 3 2 3 4 3 14 86 49 83 31 5 43 7 46 98 36 60 4 69 59 3 1 4 4 4 0 1 3 0 4 3 5 1 2 10 907139744 237517128 852012347 350549430 62876062 196019710 263351472 184393437 281593038 753973502 23 12 1 26 29 24 0 7 10 4
示例输出 1
1 2 4 120 8640 15552 1
对于第一个测试用例,每个测试用例的成本 P 如下:
- 对于 P=(1,2), \left \lfloor \frac{A_{1}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{2}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{5}{1} \right \rfloor + \left \lfloor \frac{9}{2} \right \rfloor = 9
- 对于 P=(2,1), \left \lfloor \frac{A_{2}}{2^{B_1}} \right \rfloor + \left \lfloor \frac{A_{1}}{2^{B_2}} \right \rfloor = \left \lfloor \frac{9}{1} \right \rfloor + \left \lfloor \frac{5}{2} \right \rfloor = 11
因此,最小成本是 9,并且有一种排列 P = (1,2) 实现了这一目标。
对于第二个测试用例, P = (1,2,3),(2,1,3) 实现最低成本 7.
对于第三个测试用例, P = (1,2,3,4),(2,1,3,4),(1,2,4,3),(2,1,4,3) 实现最低成本 6.
对于第四个测试用例,所有排列 (1,2,3,4,5) 实现最低成本 5000000000.