luogu#P8942. Digital Fortress

    ID: 12927 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>2023洛谷原创Special JudgeO2优化构造Ad-hoc

Digital Fortress

题目背景

布林克霍夫大声喊道:“这当然是密码!这不是密码,还能是什么?还有什么原因能让友加送掉这枚戒指?到底是谁在戒指上刻一大串杂乱无章的字母?”

方丹愤怒地等了布林克霍夫一眼,使他安静了下来。

“啊……伙计们?”贝克插了一句话,似乎很不情愿卷进来一样,“你们一直说这些是杂乱无章的字母。我想我应该让你们知道……这枚戒指上刻的字母并不是杂乱无章。如果你近距离看一下,就会明白,实际上,这些字母……这个……这个是拉丁文。”

指挥台上的所有人都看向了那枚戒指。上面写道:

Quis custodiet ipsos custiodies.
谁来监视这些监视者……

题目描述

致命的变异串已经穿过了 X-11 过滤器,深入了国安局数据库。苏珊与贝克需要即时破解出密码,以关闭蠕虫病毒。

在蠕虫的文件中,他们找到了密码的一个特点:

  • 共有 nn 位,每个数都在 [1,m][1,m] 之间,并且单调不减。
  • 如算出前缀异或和,那么前缀异或和也单调不减。
  • 如算出后缀异或和,那么后缀异或和仍然单调不减。

除此之外,他们也找到了 n,mn,m 的值。现在,他们需要构造出一组密码,以满足所有特征。


【形式化题意】

求是否存在长度为 nn,所有元素都在 [1,m][1,m] 范围内的单调不减正整数序列 aa,满足:

  • $\forall1<i\le n,a_1\ \text{xor}\ a_2\ \text{xor}\ \cdots\ \text{xor}\ a_{i-1}\le a_1\ \text{xor}\ a_2\ \text{xor}\ \cdots\ \text{xor}\ a_{i}$
  • $\forall1\le i<n,a_n\ \text{xor}\ a_{n-1}\ \text{xor}\ \cdots\ \text{xor}\ a_{i+1}\le a_n\ \text{xor}\ a_{n-1}\ \text{xor}\ \cdots\ \text{xor}\ a_{i}$

如存在,输出一组合法解。多组数据。

输入格式

第一行一个正整数 tt,表示数据组数。

对于每组数据,输入两个正整数 n,mn,m

输出格式

对于每组数据,如不存在满足要求的密码,输出 No。否则,输出 Yes,并在下一行输出一种合法方案。

2
4 20
1919 114514

Yes
1 6 8 16
No

提示

【样例解释】

对于第一组数据,密码的前缀异或和为 {1,7,15,31}\{1,7,15,31\},后缀异或和为 {16,24,30,31}\{16,24,30,31\},均为递增序列,满足题意。

对于第二组数据,不存在任何合法方案。

【数据范围】

本题开启捆绑测试。

Subtask\text{Subtask} 分值 nn\le mm\le
00 1010 55 200200
11 3030 2020 10610^6
22 6060 10510^5 26312^{63}-1

对于 100%100\% 的数据,1n1051\le n\le10^51m26311\le m\le2^{63}-11t501\le t\le50