密码锁 (expression.cpp/in/out)
时间限制: 1 s / 内存限制: 512 MB / 打开O2优化
题目描述
dyx在家里玩耍时发现了一个神奇的密码锁。然而他早已忘记了这个锁的密码,于是他随便尝试了一下,结果锁就打开了......
锁的内部有一个很长的字符串,机智的dyx马上就发现这就是密码锁的核心。于是他研究了一下午,探寻这把锁的奥秘。
他发现这个字符串是一个表达式的形式,像下面这个样子:
1 | a|b&(!c^d) |
其中,每一个由小写字母组成的单词是一个变量,对应着密码锁上的一个按钮。由于按钮只能按下或不按下,于是你可以认为每个变量是一个布尔类型的(即只有
其余的字符就只有&
、|
、^
、!
和左右小括号。dyx发现括号是用来优先运算的,意思是这是一个会将所有变量进行计算的表达式,并且优先计算括号中的子表达式。同时,&
、|
、^
、!
都是运算符,它们分别对应的是逻辑与、逻辑或、逻辑异或和逻辑非。其中前三者运算优先级一致,当它们在同一级出现时会从左至右运算,逻辑非的优先级比它们高。当每一个变量都有相应的值时,整个表达式就会就会进行计算,并给出一个布尔值。dyx还发现,当整个表达式的值为
很明显,整个密码锁的输入方案共有
不知为何,dyx又发现了一火车的密码锁。坚持不懈的dyx不停的计算着每一个密码锁能解开的方案数......由于密码锁的表达式越来越长并且人脑计算量是
输入格式
每个测试数据点有多个表达式。文件以EOF
结束。
每一个表达式占一行,且中间只有小写字母和&
、|
、^
、!
、(
、)
。
对于&
、|
和^
运算,它们左右会各有一个变量或子表达式。其运算规则如下:
& | ||
---|---|---|
| | ||
---|---|---|
^ | ||
---|---|---|
对于!
运算,它后面会有一个变量或子表达式。其运算规则如下:
! | |
---|---|
输入保证表达式是有效的,且表达式中不存在缺少参数的运算符和空的括号。
为了防止此题变成不可做的NP-hard问题,输入保证表达式中每一个变量名只出现一次。
输出格式
对于每一个表达式,输出能够解开它的方案总数。由于答案可能过大,因此将答案对
一种方案即指对每一个变量给定一个值。
两种方案不同当且仅当至少一个变量所给定的值不同。
输入样例
1 2 3 | a&b a|b|c a|!(b|c) |
输出样例
1 2 3 | 1 7 5 |
数据范围及提示
对于第一个表达式,只有
对于第二个表达式,只要三者有一个变量为
对于第三个表达式,先运算b|c
,然后对其取反,最后与
以下
对于
对于另外
对于另外
对于另外
对于另外
对于
其中