309730: CF1726B. Mainak and Interesting Sequence

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Mainak and Interesting Sequence

题意翻译

### 题目大意 认定一个长度为 $n$ 的序列 $a$ 是有趣的有且仅当满足以下条件: - 对于**任意**一个整数 $a_i$,所有**严格小于**它的数的异或和为 $0$。( 假定所有满足条件的数为 $b_j$,则异或和为 $0$ 表示 $b_1 \; xor \; b_2 \; xor \; \dots \; xor \; b_j = 0$,xor 表示按位异或 ) 请求出满足 $\sum_{i = 1}^n a_i = m$ 的长度为 $n$ 有趣的序列。 若有多种构造方式,则任意输出一种即可。 例如:$[1,3,2,3,1,2,3] , [4,4,4,4] , [25]$ 是有趣的,而 $[1,2,3,4] \; (p_2 = 1 \neq 0), \; [4,1,1,2,4] \; (p_4 = 1 \; xor \; 1 \; xor \; 2 = 2 \neq 0), \; [29,30,30] \; (p_{30} = 29 \neq 0)$不是有趣的。( 其中 $p_i$ 表示题目要求中的异或和 )。 ### 输入格式 第一行一个整数 $T \; (1 \leqslant T \leqslant 10^5)$ ,表示测试样例组数。 对于每组测试样例,包含一行两个整数 $n \; (1 \leqslant n \leqslant 10^5)$ 和 $m \; (1 \leqslant m \leqslant 10^9)$,含义见题目。 数据保证 $\sum n \leqslant 10^5$。 ### 输出格式 对于每组测试样例,如果第一行为一个字符串。如果存在满足条件的有趣的序列则输出 Yes ,否则输出 No。 如果你的输出是 Yes,则接下来的一行包含 $n$ 个数,表示你构造的序列,否则不输出这一行。 $Translated \; by \; Zigh$

题目描述

Mainak has two positive integers $ n $ and $ m $ . Mainak finds a sequence $ a_1, a_2, \ldots, a_n $ of $ n $ positive integers interesting, if for all integers $ i $ ( $ 1 \le i \le n $ ), the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all elements in $ a $ which are strictly less than $ a_i $ is $ 0 $ . Formally if $ p_i $ is the bitwise XOR of all elements in $ a $ which are strictly less than $ a_i $ , then $ a $ is an interesting sequence if $ p_1 = p_2 = \ldots = p_n = 0 $ . For example, sequences $ [1,3,2,3,1,2,3] $ , $ [4,4,4,4] $ , $ [25] $ are interesting, whereas $ [1,2,3,4] $ ( $ p_2 = 1 \ne 0 $ ), $ [4,1,1,2,4] $ ( $ p_1 = 1 \oplus 1 \oplus 2 = 2 \ne 0 $ ), $ [29,30,30] $ ( $ p_2 = 29 \ne 0 $ ) aren't interesting. Here $ a \oplus b $ denotes bitwise XOR of integers $ a $ and $ b $ . Find any interesting sequence $ a_1, a_2, \ldots, a_n $ (or report that there exists no such sequence) such that the sum of the elements in the sequence $ a $ is equal to $ m $ , i.e. $ a_1 + a_2 \ldots + a_n = m $ . As a reminder, the bitwise XOR of an empty sequence is considered to be $ 0 $ .

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases. Description of the test cases follows. The first line and the only line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5 $ , $ 1 \le m \le 10^9 $ ) — the length of the sequence and the sum of the elements. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式


For each test case, if there exists some interesting sequence, output "Yes" on the first line, otherwise output "No". You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer). If the answer is "Yes", output $ n $ positive integers $ a_1, a_2, \ldots, a_n $ ( $ a_i \ge 1 $ ), forming an interesting sequence such that $ a_1 + a_2 \ldots + a_n = m $ . If there are multiple solutions, output any.

输入输出样例

输入样例 #1

4
1 3
6 12
2 1
3 6

输出样例 #1

Yes
3
Yes
1 3 2 2 3 1
No
Yes
2 2 2

说明

- In the first test case, $ [3] $ is the only interesting sequence of length $ 1 $ having sum $ 3 $ . - In the third test case, there is no sequence of length $ 2 $ having sum of elements equal to $ 1 $ , so there is no such interesting sequence. - In the fourth test case, $ p_1 = p_2 = p_3 = 0 $ , because bitwise XOR of an empty sequence is $ 0 $ .

Input

题意翻译

### 题目大意 认定一个长度为 $n$ 的序列 $a$ 是有趣的有且仅当满足以下条件: - 对于**任意**一个整数 $a_i$,所有**严格小于**它的数的异或和为 $0$。( 假定所有满足条件的数为 $b_j$,则异或和为 $0$ 表示 $b_1 \; xor \; b_2 \; xor \; \dots \; xor \; b_j = 0$,xor 表示按位异或 ) 请求出满足 $\sum_{i = 1}^n a_i = m$ 的长度为 $n$ 有趣的序列。 若有多种构造方式,则任意输出一种即可。 例如:$[1,3,2,3,1,2,3] , [4,4,4,4] , [25]$ 是有趣的,而 $[1,2,3,4] \; (p_2 = 1 \neq 0), \; [4,1,1,2,4] \; (p_4 = 1 \; xor \; 1 \; xor \; 2 = 2 \neq 0), \; [29,30,30] \; (p_{30} = 29 \neq 0)$不是有趣的。( 其中 $p_i$ 表示题目要求中的异或和 )。 ### 输入格式 第一行一个整数 $T \; (1 \leqslant T \leqslant 10^5)$ ,表示测试样例组数。 对于每组测试样例,包含一行两个整数 $n \; (1 \leqslant n \leqslant 10^5)$ 和 $m \; (1 \leqslant m \leqslant 10^9)$,含义见题目。 数据保证 $\sum n \leqslant 10^5$。 ### 输出格式 对于每组测试样例,如果第一行为一个字符串。如果存在满足条件的有趣的序列则输出 Yes ,否则输出 No。 如果你的输出是 Yes,则接下来的一行包含 $n$ 个数,表示你构造的序列,否则不输出这一行。 $Translated \; by \; Zigh$

Output

**题目大意**

定义一个长度为 $ n $ 的序列 $ a $ 为“有趣的”当且仅当它满足以下条件:

- 对于序列中**任意**一个整数 $ a_i $,所有**严格小于**它的整数的按位异或和为 $ 0 $。(假设所有满足条件的数为 $ b_j $,则异或和为 $ 0 $ 表示 $ b_1 \oplus b_2 \oplus \dots \oplus b_j = 0 $,其中 $ \oplus $ 表示按位异或)

要求找到一个满足 $ \sum_{i = 1}^n a_i = m $ 的长度为 $ n $ 的有趣序列。如果有多种构造方式,输出其中任意一种即可。

例如,$[1,3,2,3,1,2,3] , [4,4,4,4] , [25]$ 是有趣的序列,而 $[1,2,3,4] \; (p_2 = 1 \neq 0), \; [4,1,1,2,4] \; (p_4 = 1 \oplus 1 \oplus 2 = 2 \neq 0), \; [29,30,30] \; (p_{30} = 29 \neq 0)$ 不是有趣的序列。(其中 $ p_i $ 表示题目要求中的异或和)

**输入格式**

第一行一个整数 $ T \; (1 \leqslant T \leqslant 10^5) $,表示测试样例组数。

对于每组测试样例,包含一行两个整数 $ n \; (1 \leqslant n \leqslant 10^5) $ 和 $ m \; (1 \leqslant m \leqslant 10^9) $,含义见题目。

数据保证 $ \sum n \leqslant 10^5 $。

**输出格式**

对于每组测试样例,如果存在满足条件的有趣序列则第一行输出 Yes,否则输出 No。

如果输出是 Yes,则接下来的一行包含 $ n $ 个数,表示你构造的序列,否则不输出这一行。**题目大意** 定义一个长度为 $ n $ 的序列 $ a $ 为“有趣的”当且仅当它满足以下条件: - 对于序列中**任意**一个整数 $ a_i $,所有**严格小于**它的整数的按位异或和为 $ 0 $。(假设所有满足条件的数为 $ b_j $,则异或和为 $ 0 $ 表示 $ b_1 \oplus b_2 \oplus \dots \oplus b_j = 0 $,其中 $ \oplus $ 表示按位异或) 要求找到一个满足 $ \sum_{i = 1}^n a_i = m $ 的长度为 $ n $ 的有趣序列。如果有多种构造方式,输出其中任意一种即可。 例如,$[1,3,2,3,1,2,3] , [4,4,4,4] , [25]$ 是有趣的序列,而 $[1,2,3,4] \; (p_2 = 1 \neq 0), \; [4,1,1,2,4] \; (p_4 = 1 \oplus 1 \oplus 2 = 2 \neq 0), \; [29,30,30] \; (p_{30} = 29 \neq 0)$ 不是有趣的序列。(其中 $ p_i $ 表示题目要求中的异或和) **输入格式** 第一行一个整数 $ T \; (1 \leqslant T \leqslant 10^5) $,表示测试样例组数。 对于每组测试样例,包含一行两个整数 $ n \; (1 \leqslant n \leqslant 10^5) $ 和 $ m \; (1 \leqslant m \leqslant 10^9) $,含义见题目。 数据保证 $ \sum n \leqslant 10^5 $。 **输出格式** 对于每组测试样例,如果存在满足条件的有趣序列则第一行输出 Yes,否则输出 No。 如果输出是 Yes,则接下来的一行包含 $ n $ 个数,表示你构造的序列,否则不输出这一行。

加入题单

上一题 下一题 算法标签: