逻辑表达式
题目描述
给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：
& 表示逻辑与运算
| 表示逻辑或运算
^ 表示逻辑异或运算
表达式还包含三种基本逻辑值：0、1、?。
每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？
由于答案可能很大，请输出方案数模1,000,000,007 的余数。
前缀表达式的定义如下：
0、1、? 都是前缀表达式；
如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；
不满足以上两条规则的表达式都不是前缀表达式。
输入格式
单个字符串表示输入的前缀表达式
输出格式
单个整数：表示答案模 1,000,000,007 的余数。
输入样例#1
&??
输出样例#1
3
输入样例#2
||??|||?^?|0|1&???|??
输出样例#2
4
输入样例#3
|?^?|0|&??||?^?|1??
输出样例#3
64
说明提示
设 ∣s∣表示输入字符串的长度
50%的数据，1≤∣s∣<1,000
100%的数据，1≤∣s∣<200,000
限制
时间限制：1000ms
内存限制：512MiB
相似题推荐
专属教室
题目描述
在一所学校中，有 N 个班级，每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si，但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同，所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室，且一次只能安排一个班级进行更换。在更换时，目标教室必须是空闲的。
学校希望找到一个合理的更换顺序，使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行，每行两个字符串 Si 和 Ti，表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换，输出 Yes，否则输出 No。
输入样例#1
2 b m m d
输出样例#1
Yes
输入样例#2
3 a b b c c a
输出样例#2
No
说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串，长度在 1 到 8 之间。
Si≠Ti
所有 Si 互不相同。
所有 Ti 互不相同。
限制
时间限制：1000ms
内存限制：256MiB
