310135: CF1787E. The Harmonization of XOR
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
The Harmonization of XOR
题意翻译
### 题目描述 给定 $n$ 个数 $[1,2,3,\ldots,n]$ 和两个正整数 $k$ 和 $x$。 将这些数分成恰好 $k$ 组使得每组的异或和都是 $x$。具体地，每个数都必须出现在恰好一组内。 例如，$n = 15,k = 6,x = 7$ 时，下列分法是合法的（$\oplus$ 表示按位异或运算）： - $[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$ 下列分法是不合法的： - $[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$ 因为 $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$, - $[3,4]$, $3 \oplus 4 = 7$, - $[8,15]$, $8 \oplus 15 = 7$, - $[7]$, $7 = 7$. 因为 $1$ 和 $2$ 未出现且 $3$ 出现两次。 ~~这题本来是 C~~ ### 输入格式 第一行一个正整数 $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$），含义见题目描述。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 输出格式 对于每组测试数据，若不存在合法方案，输出 `NO`。若存在，先输出 `YES`，接下来 $k$ 行输出方案。具体地，每一行第一个数字输出这一组的长度 $s_i$，后接 $s_i$ 个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。 ### 样例解释 第一组测试数据中，给出的一组合法方案如下： - $[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$ 第二组测试数据中，给出的一组合法方案如下： - $[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$题目描述
You are given an array of exactly $ n $ numbers $ [1,2,3,\ldots,n] $ along with integers $ k $ and $ x $ . Partition the array in exactly $ k $ non-empty disjoint subsequences such that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all numbers in each subsequence is $ x $ , and each number is in exactly one subsequence. Notice that there are no constraints on the length of each subsequence. A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements. For example, for $ n = 15 $ , $ k = 6 $ , $ x = 7 $ , the following scheme is valid: - $ [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 $ , where $ \oplus $ represents the bitwise XOR operation.The following scheme is invalid, since $ 8 $ , $ 15 $ do not appear: - $ [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 $ . The following scheme is invalid, since $ 3 $ appears twice, and $ 1 $ , $ 2 $ do not appear: - $ [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 $ .输入输出格式
输入格式
Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first and the only line of each test case contains three integers $ n $ , $ k $ , $ x $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ; $ 1\le x \le 10^9 $ ) — the length of the array, the number of subsequences and the required XOR. It's guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, if it is possible to partition the sequence, print "YES" in the first line. In the $ i $ -th of the following $ k $ lines first print the length $ s_i $ of the $ i $ -th subsequence, then print $ s_i $ integers, representing the elements in the $ i $ -th subsequence. If there are multiple answers, print any. Note that you can print a subsequence in any order. If it is not possible to partition the sequence, print "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说明
In the first test case, we construct the following $ 6 $ subsequences: - $ [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 $ . In the second test case, we construct the following $ 4 $ subsequences: - $ [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 $ . The following solution is considered correct in this test case as well: - $ [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 $ .Input
题意翻译
### 题目描述 给定 $n$ 个数 $[1,2,3,\ldots,n]$ 和两个正整数 $k$ 和 $x$。 将这些数分成恰好 $k$ 组使得每组的异或和都是 $x$。具体地，每个数都必须出现在恰好一组内。 例如，$n = 15,k = 6,x = 7$ 时，下列分法是合法的（$\oplus$ 表示按位异或运算）： - $[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$ 下列分法是不合法的： - $[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$ 因为 $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$, - $[3,4]$, $3 \oplus 4 = 7$, - $[8,15]$, $8 \oplus 15 = 7$, - $[7]$, $7 = 7$. 因为 $1$ 和 $2$ 未出现且 $3$ 出现两次。 ~~这题本来是 C~~ ### 输入格式 第一行一个正整数 $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$），含义见题目描述。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 输出格式 对于每组测试数据，若不存在合法方案，输出 `NO`。若存在，先输出 `YES`，接下来 $k$ 行输出方案。具体地，每一行第一个数字输出这一组的长度 $s_i$，后接 $s_i$ 个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。 ### 样例解释 第一组测试数据中，给出的一组合法方案如下： - $[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$ 第二组测试数据中，给出的一组合法方案如下： - $[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$Output
**题目大意**：
给定一个数组，数组包含从1到n的连续整数，以及两个正整数k和x。要求将这个数组分成恰好k组，使得每组的异或和都是x。每个数字必须恰好出现在一组中。你需要判断是否存在这样的分组方法，如果存在，输出分组方案，否则输出`NO`。
**输入格式**：
第一行包含一个正整数t（1≤t≤10^4），表示测试数据的组数。
每组测试数据包含一行，有三个正整数n, k, x（1≤k≤n≤2×10^5，1≤x≤10^9），分别表示数组的长度、分组的数量和要求的异或和。
保证所有测试数据的n之和不超过2×10^5。
**输出格式**：
对于每组测试数据，如果不存在合法方案，输出`NO`。如果存在，先输出`YES`，接下来k行输出方案。具体来说，每一行的第一个数字输出这一组的长度s_i，后接s_i个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。
**样例解释**：
在第一组测试数据中，输出了一组合法方案，例如[6,10,11]，6⊕10⊕11=7等。
在第二组测试数据中，输出了一组合法方案，例如[1,4]，1⊕4=5等。同时还有另一组合法方案，例如[1,4]，1⊕4=5等。
输入输出样例已给出，包括合法和不合法的方案。**题目大意**： 给定一个数组，数组包含从1到n的连续整数，以及两个正整数k和x。要求将这个数组分成恰好k组，使得每组的异或和都是x。每个数字必须恰好出现在一组中。你需要判断是否存在这样的分组方法，如果存在，输出分组方案，否则输出`NO`。 **输入格式**： 第一行包含一个正整数t（1≤t≤10^4），表示测试数据的组数。 每组测试数据包含一行，有三个正整数n, k, x（1≤k≤n≤2×10^5，1≤x≤10^9），分别表示数组的长度、分组的数量和要求的异或和。 保证所有测试数据的n之和不超过2×10^5。 **输出格式**： 对于每组测试数据，如果不存在合法方案，输出`NO`。如果存在，先输出`YES`，接下来k行输出方案。具体来说，每一行的第一个数字输出这一组的长度s_i，后接s_i个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。 **样例解释**： 在第一组测试数据中，输出了一组合法方案，例如[6,10,11]，6⊕10⊕11=7等。 在第二组测试数据中，输出了一组合法方案，例如[1,4]，1⊕4=5等。同时还有另一组合法方案，例如[1,4]，1⊕4=5等。 输入输出样例已给出，包括合法和不合法的方案。
给定一个数组，数组包含从1到n的连续整数，以及两个正整数k和x。要求将这个数组分成恰好k组，使得每组的异或和都是x。每个数字必须恰好出现在一组中。你需要判断是否存在这样的分组方法，如果存在，输出分组方案，否则输出`NO`。
**输入格式**：
第一行包含一个正整数t（1≤t≤10^4），表示测试数据的组数。
每组测试数据包含一行，有三个正整数n, k, x（1≤k≤n≤2×10^5，1≤x≤10^9），分别表示数组的长度、分组的数量和要求的异或和。
保证所有测试数据的n之和不超过2×10^5。
**输出格式**：
对于每组测试数据，如果不存在合法方案，输出`NO`。如果存在，先输出`YES`，接下来k行输出方案。具体来说，每一行的第一个数字输出这一组的长度s_i，后接s_i个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。
**样例解释**：
在第一组测试数据中，输出了一组合法方案，例如[6,10,11]，6⊕10⊕11=7等。
在第二组测试数据中，输出了一组合法方案，例如[1,4]，1⊕4=5等。同时还有另一组合法方案，例如[1,4]，1⊕4=5等。
输入输出样例已给出，包括合法和不合法的方案。**题目大意**： 给定一个数组，数组包含从1到n的连续整数，以及两个正整数k和x。要求将这个数组分成恰好k组，使得每组的异或和都是x。每个数字必须恰好出现在一组中。你需要判断是否存在这样的分组方法，如果存在，输出分组方案，否则输出`NO`。 **输入格式**： 第一行包含一个正整数t（1≤t≤10^4），表示测试数据的组数。 每组测试数据包含一行，有三个正整数n, k, x（1≤k≤n≤2×10^5，1≤x≤10^9），分别表示数组的长度、分组的数量和要求的异或和。 保证所有测试数据的n之和不超过2×10^5。 **输出格式**： 对于每组测试数据，如果不存在合法方案，输出`NO`。如果存在，先输出`YES`，接下来k行输出方案。具体来说，每一行的第一个数字输出这一组的长度s_i，后接s_i个数字表示这一组的数字。注意每一组中的数字可以按任意顺序给出。 **样例解释**： 在第一组测试数据中，输出了一组合法方案，例如[6,10,11]，6⊕10⊕11=7等。 在第二组测试数据中，输出了一组合法方案，例如[1,4]，1⊕4=5等。同时还有另一组合法方案，例如[1,4]，1⊕4=5等。 输入输出样例已给出，包括合法和不合法的方案。