#P18272. Boolean Function Reconstruction

Boolean Function Reconstruction

Boolean Function Reconstruction

给定一个以 nn 个布尔变量为输入的布尔函数的完整真值表,请构造一个实现该函数的布尔表达式。只能使用逻辑与 & 和逻辑或 |,不能使用取反。

合法表达式 <expr> 必须严格符合以下递归语法:

  • T、F:分别表示真、假。
  • a、b、……:第 ii 个变量用第 ii 个小写英文字母表示,只能使用本测试用例给出的 nn 个变量。
  • (<expr>&<expr>):两个表达式的逻辑与。
  • (<expr>|<expr>):两个表达式的逻辑或。

两种运算的真值表如下。

x1x_1 x2x_2 x1&x2x_1\&x_2 x1∣x2x_1\mathbin{\vert}x_2
0 0 0 0
1 1
1 0
1

判断是否存在符合要求的表达式。若存在,你输出的表达式中,二元运算符(& 和 |)的总数不得超过 2n−1+102^{n-1}+10,括号嵌套深度不得超过 100100。可以证明,只要该函数能够用上述运算表示,就一定有满足这两个限制的表达式。

输入格式

第一行一个整数 TT,表示测试用例数,1≤T≤2161\le T\le2^{16}。

每个测试用例占两行:

  • 第一行一个整数 nn,1≤n≤151\le n\le15。
  • 第二行一个长度恰为 2n2^n 的二进制字符串 ss,表示函数真值表。

具体地,当第 ii 个变量的取值为 xix_i 时,函数值等于字符串 ss 的第

1+∑i=1nxi2i−11+\sum_{i=1}^{n}x_i2^{i-1}

个字符(字符串下标从 11 开始)。因此,变量 a 对应二进制下标的最低位。

保证同一输入文件内所有测试用例满足

∑22n≤230.\sum 2^{2n}\le2^{30}.

输出格式

每个测试用例先输出一行 Yes 或 No,表示是否存在满足要求的表达式。

若输出 Yes,下一行输出一个合法表达式。表达式必须严格遵守上述格式,不得添加或省略括号,也不得含有额外空格。可以输出任意一个满足真值表、运算符数量和嵌套深度限制的表达式。

样例输入

7
2
0001
2
0111
2
1111
3
00010111
1
10
2
0101
5
00000000000000000000000000000001

样例输出

Yes
(a&b)
Yes
(a|b)
Yes
T
Yes
((a&(b|c))|(b&c))
No
Yes
a
Yes
(a&(b&(c&(d&e))))

样例说明

第四个测试用例的真值表如下(列顺序与原题一致,x1x_1 对应 a)。

x3x_3 x2x_2 x1x_1 f(x1,x2,x3)f(x_1,x_2,x_3)
0 0 0 0
1
1 0
1
1 0 0
1 1
1 0
1

表达式 ((a&(b|c))|(b&c)) 满足该真值表。其他等价且满足限制的表达式也合法。