3994. 布尔表达式

单点时限: 2.5 sec

内存限制: 512 MB

请你构造一个 $n$ 维布尔函数 $f(a_1,a_2,\ldots,a_n)$,使得它满足给定的真值表。$f$ 使用布尔表达式来构造。

一个布尔表达式包含以下符号:

  • 变量名:由字母 a、数字组成。变量的类型只能为布尔类型,其值为真(用 $1$ 表示)或者假(用 $0$ 表示)。
  • 运算符:逻辑与($\wedge$)、逻辑或($\vee$)、逻辑非($\neg$)。
  • m 常量:$1$ 或者 $0$。

运算符使用方式与计算方式:

  • 逻辑与:二元运算符,写作 $a\wedge b$。当且仅当 $a,b$ 都为真,$a\wedge b$ 才为真。
  • 逻辑或:二元运算符,写作 $a\vee b$。当且仅当 $a,b$ 都为假,$a\wedge b$ 才为假。
  • 逻辑非:一元运算符,写作 $\neg a$。当且仅当 $a$ 为真,$\neg a$ 才为假。

运算符优先级从高到低的顺序依次是:逻辑非、逻辑与、逻辑或。

运算符的结合律均为右结合。例如 $a\wedge b\wedge c=a\wedge (b\wedge c)$,$\neg\neg\neg a=\neg(\neg(\neg a))$。

如果有多个可能的构造,输出任意一个即可。

输入格式

第一行一个整数 $n$($1\le n\le 16$)。

接下来一个长度为 $2^n$ 的01串 $s_0s_1\ldots s_{2^n-1}$,其中 $s_i$ 表示当 $(\overline{a_1a_2\ldots a_n})_2=i$ 时 $f(a_1,\ldots,a_n)$ 的值。$s_i=0$ 表示值为假,$s_i=1$ 表示值为真。

$(\overline{a_1\ldots a_n})_2$ 表示二进制下的 $\overline{a_1\ldots a_n}$ 的十进制值,例如 $(\overline{0101})_2=5$。

输出格式

输出一个布尔表达式表示 $f$。

输出方式:

  • 变量:$a_i$ 写作 ai。如 $a_5$ 写作 a5
  • 常量:$1$ 写作 1,$0$ 写作 0
  • 逻辑与:$\wedge$ 写作 A。例如 $a_{10}\wedge a_{11}$ 写作 a10 A a11,注意运算符与变量之间的 空格
  • 逻辑或:$\vee$ 写作 O。例如 $a_{10}\vee a_{11}$ 写作 a10 O a11,注意运算符与变量之间的 空格
  • 逻辑非:$\neg$ 写作 N。例如 $\neg a_1$ 写作 N a1,注意运算符与变量之间的 空格

请注意行末不要输出多余的空格。

样例

Input
2
0001
Output
a2 A a1 A a2
Input
3
11110001
Output
N a1 O a2 A a3 O N 1

提示

对于第一个样例,读入的信息为

  • $a_1=0,a_2=0,f(a_1,a_2)=0$。
  • $a_1=0,a_2=1,f(a_1,a_2)=0$。
  • $a_1=1,a_2=0,f(a_1,a_2)=0$。
  • $a_1=1,a_2=1,f(a_1,a_2)=1$。

一个可能的构造是 $f(a_1,a_2)=a_1\wedge a_2$,或者 $f(a_1,a_2)=a_2\wedge a_1\wedge a_2$。

对于第二个样例,一个可能的构造是 $f(a_1,a_2,a_3) = \neg a_1\vee a_2\wedge a_3$。

106 人解决,123 人已尝试。

147 份提交通过,共有 491 份提交。

3.1 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 3 周,2 天前.

来源: EOJ Monthly 2020.11

题目标签