1008. 今晚吃 NPC

题目描述

我们知道，布尔可满足性问题（SAT）是经典的 NPC 问题。

然而 NPC 问题不过是 Lv.0 身上才存在的枷锁。作为拥有超强计算力的空间系能力者白井黑子，在脑中模拟非确定性图灵机并快速计算出 NPC 问题的解毫无难度。

然而黑子太忙了，所以她决定让你帮她计算一个比 SAT 更难的问题，该问题引入了异或运算。她相信，这个有趣的问题，无疑是善良的黑子大人无私的馈赠；这个美妙的题目，一定可以给拼搏于图灵奖的逐梦之路上的你，提供一个有力的援助。

形式化地，给定一个位运算方程 $x_1\,op_1\,x_2\,op_2\,x_3\,op_3\cdots x_{n-1}\,op_{n-1}\,x_n=w$，其中：

• $x_1,x_2,x_3,\cdots,x_n$ 是 $n$ 个独立的未知数；
• $op_1,op_2,op_3,\cdots,op_{n-1}$ 是 $n-1$ 个给定的运算符，每个运算符都是 $\mathrm{and},\mathrm{xor},\mathrm{or}$ 中的一个，三个运算符的优先级是 $\mathrm{and}$ 先于 $\mathrm{xor}$ 先于 $\mathrm{or}$；
• $w$ 是给定的参数。

你需要为该方程找到一组非负整数解，满足 $0\le x_1,x_2,\cdots x_n<2^{31}$，若无法找到任何一组解则报告无解。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 10^5$）表示你需要解决的问题的数量。

接下来对于每一个问题：

第一行包含两个整数 $n,w$（$2\le n\le10^5$，$\sum n\le 1.2\times 10^6$，$0\le w<2^{31}$），表示变量的数量与给定参数值。

第二行包含一个长度为 $n-1$ 的字符串 $op_1op_2op_3\cdots op_{n-1}$（$op_1,op_2,op_3,\cdots,op_{n-1}$ 均为 &，^，| 中的一个），表示方程中的每个运算符，其中 & 代表 $\mathrm{and}$，^ 代表 $\mathrm{xor}$，| 代表 $\mathrm{or}$。

输出格式

本题启用 Special Judge 评测。

对于每一个问题：

若存在解，输出的第一行包含一个字符串 Yes，第二行包含 $n$ 个非负整数 $x_1,x_2,x_3,\cdots,x_n$（$0\le x_1,x_2,x_3,\cdots,x_n<2^{31}$）表示你找出的解，用空格分隔。若存在多组解，输出任意一组都算作正确。

若不存在解，输出包含一行一个字符串 No。

样例输入

2
4 3
&|^
7 0
^^^^^^

样例输出

Yes
3 1 0 2
Yes
1 2 3 4 5 6 7

提示

对于第一组样例：

$$\begin{aligned} &3\ \mathrm{and}\ 1\ \mathrm{or}\ 0\ \mathrm{xor}\ 2\\ =\ &1\ \mathrm{or}\ 0\ \mathrm{xor}\ 2\\ =\ &1\ \mathrm{or}\ 2\\ =\ &3\\ \end{aligned}$$

因此其为符合约束的一组解。

提示：按位与（$\mathrm{and}$）、按位异或$（\mathrm{xor}$）、按位或$（\mathrm{or}$）是对数字二进制位进行操作的三种基础运算：

• 按位与：两个数的对应二进制位都为 1 时，结果位才是 1，其他情况都是 0。
• 按位异或：两个数的对应二进制位不同时，结果位是 1，否则结果位是 0。
• 按位或：两个数的对应二进制位都为 0 时，结果位才是 0，其他情况都是 1。

接下来我们拿 $5$（二进制为 $\lparen 0101\rparen_2$）和 $9$（二进制为 $\lparen 1001\rparen_2$）作为例子。

• 按位与：$\lparen 0101\rparen_2\,\mathrm{and}\,\lparen 1001\rparen_2=\lparen 0001\rparen_2$，故 $5\,\mathrm{and}\,9=1$。
• 按位异或：$\lparen 0101\rparen_2\,\mathrm{xor}\,\lparen 1001\rparen_2=\lparen 1100\rparen_2$，故 $5\,\mathrm{xor}\,9=12$。
• 按位或：$\lparen 0101\rparen_2\,\mathrm{or}\,\lparen 1001\rparen_2=\lparen 1101\rparen_2$，故 $5\,\mathrm{or}\,9=13$。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1008 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。