← 返回题目列表

Codeforces · 1787/E

E. XOR 的协调

中文机器翻译题面 查看原题

给你一个由 $$$n$$$ 数字 $$$[1,2,3,\ldots,n]$$$ 以及整数 $$$k$$$ 和 $$$x$$$ 组成的数组。

将数组精确划分为 $$$k$$$ 个非空不相交子序列,使得每个子序列中所有数字的按位异或为 $$$x$$$,并且每个数字恰好位于一个子序列中。请注意,每个子序列的长度没有限制。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。

例如,对于 $$$n = 15$$$、$$$k = 6$$$、$$$x = 7$$$,以下方案有效:

- $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
- $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
- $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
- $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
- $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
- $$$[7]$$$, $$$7 = 7$$$,

以下方案无效,因为 $$$8$$$、$$$15$$$ 未出现:

- $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
- $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
- $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
- $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
- $$$[7]$$$, $$$7 = 7$$$.

以下方案无效,因为 $$$3$$$ 出现了两次,并且 $$$1$$$、$$$2$$$ 没有出现:

- $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
- $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
- $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
- $$$[3,4]$$$, $$$3 \oplus 4 = 7$$$,
- $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
- $$$[7]$$$, $$$7 = 7$$$.

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$k$$$、$$$x$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$; $$$1\le x \le 10^9$$$) — 数组的长度、子序列的数量和所需的 XOR。

保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以对序列进行分区,请在第一行打印“YES”。在接下来的 $$$k$$$ 行的第 $$$i$$$ 行中,首先打印第 $$$i$$$ 个子序列的长度 $$$s_i$$$,然后打印 $$$s_i$$$ 整数,表示第 $$$i$$$ 个子序列中的元素。如果有多个答案,请打印其中一个。请注意,您可以按任何顺序打印子序列。

如果无法对序列进行分区,则打印“NO”。

示例

输入 #1

7
15 6 7
11 4 5
5 3 2
4 1 4
6 1 7
11 5 5
11 6 5

输出 #1

YES
3 6 10 11
3 5 12 14
3 3 9 13
3 1 2 4
2 8 15
1 7
YES
2 1 4
2 2 7
2 3 6
5 5 8 9 10 11
NO
YES
4 1 2 3 4
YES
6 1 2 3 4 5 6
NO
NO

注意

在第一个测试用例中,我们构造以下 $$$6$$$ 子序列:

- $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,
- $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,
- $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,
- $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,
- $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,
- $$$[7]$$$, $$$7 = 7$$$.

在第二个测试用例中,我们构造以下 $$$4$$$ 子序列:

- $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,
- $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,
- $$$[3,6]$$$, $$$3 \oplus 6 = 5$$$,
- $$$[5,8,9,10,11]$$$,$$$5 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$。

在此测试用例中,以下解决方案也被认为是正确的:

- $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,
- $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,
- $$$[5]$$$, $$$5 = 5$$$,
- $$$[3,6,8,9,10,11]$$$,$$$3 \oplus 6 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$。