#P8942. Digital Fortress
Digital Fortress
题目背景
布林克霍夫大声喊道:“这当然是密码!这不是密码,还能是什么?还有什么原因能让友加送掉这枚戒指?到底是谁在戒指上刻一大串杂乱无章的字母?”
方丹愤怒地等了布林克霍夫一眼,使他安静了下来。
“啊……伙计们?”贝克插了一句话,似乎很不情愿卷进来一样,“你们一直说这些是杂乱无章的字母。我想我应该让你们知道……这枚戒指上刻的字母并不是杂乱无章。如果你近距离看一下,就会明白,实际上,这些字母……这个……这个是拉丁文。”
指挥台上的所有人都看向了那枚戒指。上面写道:
Quis custodiet ipsos custiodies.
谁来监视这些监视者……
题目描述
致命的变异串已经穿过了 X-11 过滤器,深入了国安局数据库。苏珊与贝克需要即时破解出密码,以关闭蠕虫病毒。
在蠕虫的文件中,他们找到了密码的一个特点:
- 共有 位,每个数都在 之间,并且单调不减。
- 如算出前缀异或和,那么前缀异或和也单调不减。
- 如算出后缀异或和,那么后缀异或和仍然单调不减。
除此之外,他们也找到了 的值。现在,他们需要构造出一组密码,以满足所有特征。
【形式化题意】
求是否存在长度为 ,所有元素都在 范围内的单调不减正整数序列 ,满足:
- $\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}$
如存在,输出一组合法解。多组数据。
输入格式
第一行一个正整数 ,表示数据组数。
对于每组数据,输入两个正整数 。
输出格式
对于每组数据,如不存在满足要求的密码,输出 No
。否则,输出 Yes
,并在下一行输出一种合法方案。
2
4 20
1919 114514
Yes
1 6 8 16
No
提示
【样例解释】
对于第一组数据,密码的前缀异或和为 ,后缀异或和为 ,均为递增序列,满足题意。
对于第二组数据,不存在任何合法方案。
【数据范围】
本题开启捆绑测试。
分值 | |||
---|---|---|---|
对于 的数据,,,。