分数: 900 点
问题陈述
给你一个正整数 N.
输出一对非负整数序列 P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N) 满足以下所有条件:
- 0 \leq P_i < 2^{30}~(1 \leq i \leq N)
- 0 \leq A_i < 2^{30}~(1 \leq i \leq N)
- 的最长严格递增子序列的长度 (P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i) is i. (1 \leq i \leq N)
- \mathrm{OR} 表示按位 \mathrm{OR} 操作。
可以证明,在该问题的约束下,至少存在一对 P, A 满足条件。
解决 T 每个输入的测试用例。
什么是按位 \mathrm{OR}?
按位 \mathrm{OR} 非负整数 A, B,表示 A\ \mathrm{OR}\ B,定义如下:
- 当 A\ \mathrm{OR}\ B 以二进制形式写入,位置处的数字 2^k (k \geq 0) 是 1 如果位置处至少有一位数字 2^k 的二进制表示形式 A 和 B is 1,和 0 否则。
约束
- 1 \leq T
- 1 \leq N \leq 1024
- 对于单个输入中的测试用例, N 最多是 200000.
- 对于单个输入中的测试用例, N^2 最多是 1024^2.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N
输出
输出一个解决方案 \mathrm{case}_1, \mathrm{case}_2, \dots, \mathrm{case}_T 按此顺序。
对于每种情况,按以下格式输出答案:
P_1 P_2 \ldots P_N A_1 A_2 \ldots A_N
如果有多个解决方案,则其中任何一个都将被视为正确。
示例输入 1
3 3 8 1
示例输出 1
3 14 5 13 2 10 6 902 909 186 684 219 471 248 1023 249 64 0 264 768 778 794 2025 1026
对于第一个测试用例,示例输出为 P = (3, 14, 5), A = (13, 2, 10).
- 一个最长的严格递增子序列 (3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13) is (13),其长度为 1.
- 一个最长的严格递增子序列 (3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7) is (3, 7),其长度为 2.
- 一个最长的严格递增子序列 (3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15) is (11, 14, 15),其长度为 3.
由上可以确认 P = (3, 14, 5), A = (13, 2, 10) 满足条件。